A Note on Optimizing the Ratio of Monotone Supermodular Functions
arXiv:2012.09725v1
AI Analysis
This work establishes a fundamental hardness result for a class of optimization problems relevant to various fields where supermodular functions are used, impacting researchers and practitioners seeking efficient approximation algorithms.
This paper demonstrates that optimizing the ratio of two monotone supermodular functions (either both non-decreasing or both non-increasing) cannot achieve a bounded approximation ratio using a polynomial number of queries.
We show that for the problem of minimizing (or maximizing) the ratio of two supermodular functions, no bounded approximation ratio can be achieved via polynomial number of queries, if the two supermodular functions are both monotone non-decreasing or non-increasing.