Algorithms for Optimizing the Ratio of Submodular Functions


Wenruo Bai, Rishabh Iyer, Kai Wei, Jeff Bilmes ;
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2751-2759, 2016.


We investigate a new optimization problem involving minimizing the Ratio of Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems, including minimizing the difference of submodular functions, and to submodular optimization subject to submodular constraints. We show RS that optimization can be solved within bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a \log factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.

Related Material