Optimizing Ratio of Monotone Set Functions

Optimizing Ratio of Monotone Set Functions

Chao Qian, Jing-Cheng Shi, Yang Yu, Ke Tang, Zhi-Hua Zhou

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 2606-2612. https://doi.org/10.24963/ijcai.2017/363

This paper considers the problem of minimizing the ratio of two set functions, i.e., $f/g$. Previous work assumed monotone and submodular of the two functions, while we consider a more general situation where $g$ is not necessarily submodular. We derive that the greedy approach GreedRatio, as a fixed time algorithm, achieves a $\frac{|X^*|}{(1+(|X^*| \textendash 1)(1 \textendash \kappa_f))\gamma(g)}$ approximation ratio, which also improves the previous bound for submodular $g$. If more time can be spent, we present the PORM algorithm, an anytime randomized iterative approach minimizing $f$ and $\textendash g$ simultaneously. We show that PORM using reasonable time has the same general approximation guarantee as GreedRatio, 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