On Subset Selection with General Cost Constraints
Abstract
This paper considers the subset selection problem with a monotone objective function and a monotone cost constraint, which relaxes the submodular property of previous studies. We first show that the approximation ratio of the generalized greedy algorithm is $\frac{\alpha}{2}(1 \textendash \frac{1}{e^{\alpha}})$ (where $\alpha$ is the submodularity ratio); and then propose POMC, an anytime randomized iterative approach that can utilize more time to find better solutions than the generalized greedy algorithm. We show that POMC can obtain the same general approximation guarantee as the generalized greedy algorithm, but can achieve better solutions in cases and applications.
Cite
Text
Qian et al. "On Subset Selection with General Cost Constraints." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/364Markdown
[Qian et al. "On Subset Selection with General Cost Constraints." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/qian2017ijcai-subset/) doi:10.24963/IJCAI.2017/364BibTeX
@inproceedings{qian2017ijcai-subset,
title = {{On Subset Selection with General Cost Constraints}},
author = {Qian, Chao and Shi, Jing-Cheng and Yu, Yang and Tang, Ke},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {2613-2619},
doi = {10.24963/IJCAI.2017/364},
url = {https://mlanthology.org/ijcai/2017/qian2017ijcai-subset/}
}