Structure and Learning of Valuation Functions

被引：0

作者：

Feldman, Vitaly ^{[1
]}

Vondrak, Jan ^{[1
]}

机构：

[1] IBM Corp, Almaden Res Ctr, San Jose, CA 95120 USA

来源：

ACM SIGECOM EXCHANGES | 2013年 / 12卷 / 02期

关键词：

Valuation Functions; Submodular Functions; PAC Learning; Economics; Theory;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We discuss structural results and learning algorithms for submodular and fractionally subadditive valuation functions. While learning these valuation functions over general distributions turns out to be hard, we present compact approximate representations and efficient learning algorithms for such functions over the uniform distribution.

引用

页码：50 / 53

页数：4

共 15 条

[1] Balcan MF, 2011, ACM S THEORY COMPUT, P793
[2] Balcan Maria-Florina, 2012, COLT JMLR, V23, P4
[3] Boucheron S, 2000, RANDOM STRUCT ALGOR, V16, P277, DOI 10.1002/(SICI)1098-2418(200005)16:3<277::AID-RSA4>3.0.CO
[4] 2-1
[5] On the distribution of the Fourier spectrum of Boolean functions
Bourgain, J
[J]. ISRAEL JOURNAL OF MATHEMATICS, 2002, 131 (1) : 269 - 276
[6] Cheraghchi Mahdi, 2012, SODA, P1586
[7] On the hardness of approximating minimum vertex cover
Dinur, I
Safra, S
[J]. ANNALS OF MATHEMATICS, 2005, 162 (01) : 439 - 485
[8] Feldman V., 2013, P COLT
[9] Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas
Feldman, Vitaly
Vondrak, Jan
[J]. 2013 IEEE 54TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2013, : 227 - 236
[10] Boolean functions with low average sensitivity depend on few coordinates
Friedgut, E
[J]. COMBINATORICA, 1998, 18 (01) : 27 - 35

← 1 2 →