Optimizing Ratio of Monotone Set Functions
Abstract
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.
Cite
Text
Qian et al. "Optimizing Ratio of Monotone Set Functions." International Joint Conference on Artificial Intelligence, 2017. doi:10.24963/IJCAI.2017/363Markdown
[Qian et al. "Optimizing Ratio of Monotone Set Functions." International Joint Conference on Artificial Intelligence, 2017.](https://mlanthology.org/ijcai/2017/qian2017ijcai-optimizing/) doi:10.24963/IJCAI.2017/363BibTeX
@inproceedings{qian2017ijcai-optimizing,
title = {{Optimizing Ratio of Monotone Set Functions}},
author = {Qian, Chao and Shi, Jing-Cheng and Yu, Yang and Tang, Ke and Zhou, Zhi-Hua},
booktitle = {International Joint Conference on Artificial Intelligence},
year = {2017},
pages = {2606-2612},
doi = {10.24963/IJCAI.2017/363},
url = {https://mlanthology.org/ijcai/2017/qian2017ijcai-optimizing/}
}