# On Subset Selection with General Cost Constraints

# On Subset Selection with General Cost Constraints

## Chao Qian, Jing-Cheng Shi, Yang Yu, Ke Tang

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence

Main track. Pages 2613-2619.
https://doi.org/10.24963/ijcai.2017/364

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.

Keywords:

Machine Learning: Machine Learning

Combinatorial & Heuristic Search: Heuristic Search

Combinatorial & Heuristic Search: Combinatorial search/optimisation