Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection
Abstract
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.
Cite
Text
Qian et al. "Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection." International Joint Conference on Artificial Intelligence, 2018. doi:10.24963/IJCAI.2018/205Markdown
[Qian et al. "Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection." International Joint Conference on Artificial Intelligence, 2018.](https://mlanthology.org/ijcai/2018/qian2018ijcai-approximation/) doi:10.24963/IJCAI.2018/205BibTeX
@inproceedings{qian2018ijcai-approximation,
title = {{Approximation Guarantees of Stochastic Greedy Algorithms for Subset Selection}},
author = {Qian, Chao and Yu, Yang and Tang, Ke},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2018},
pages = {1478-1484},
doi = {10.24963/IJCAI.2018/205},
url = {https://mlanthology.org/ijcai/2018/qian2018ijcai-approximation/}
}