Approximation guarantees of stochastic greedy algorithms for subset selection

Qian，Chao1; Yu，Yang2; Tang，Ke3

2018

1045-0823

IJCAI International Joint Conference on Artificial Intelligence

2018-July

1478-1484

Stockholm, Sweden

International Joint Conferences on Artificial Intelligence

Subset selection is a fundamental problem in many areas, which aims to select the best subset of size at most k from a universe. Greedy algorithms are widely used for subset selection, and have shown good approximation performances in deterministic situations. However, their behaviors are stochastic in many realistic situations (e.g., large-scale and noisy). For general stochastic greedy algorithms, bounded approximation guarantees were obtained only for subset selection with monotone submodular objective functions, while real-world applications often involve non-monotone or non-submodular objective functions and can be subject to a more general constraint than a size constraint. This work proves their approximation guarantees in these cases, and thus largely extends the applicability of stochastic greedy algorithms.

其他

英语

EI

[BK20160066] ; [NA150123] ; Shenzhen Science and Technology Innovation Commission[ZDSYS201703031748284] ; National Natural Science Foundation of China[61672478] ; National Natural Science Foundation of China[61603367]

20184406016147

Approximation algorithms ; Artificial intelligence ; Set theory

Artificial Intelligence:723.4 ; Mathematics:921 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Systems Science:961

2-s2.0-85055687962

Scopus

1.,Anhui Province Key Lab of Big Data Analysis and Application,University of Science and Technology of China,Hefei,230027,China
2.,National Key Lab for Novel Software Technology,Nanjing University,Nanjing,210023,China
3.,Shenzhen Key Lab of Computational Intelligence,Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China

Qian，Chao,Yu，Yang,Tang，Ke. Approximation guarantees of stochastic greedy algorithms for subset selection[C]:International Joint Conferences on Artificial Intelligence,2018:1478-1484.