A Note on Optimizing the Ratio of Monotone Supermodular Functions
share
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.
READ FULL TEXT