论文标题
关于优化单调超模块函数比率的注释
A Note on Optimizing the Ratio of Monotone Supermodular Functions
论文作者
论文摘要
我们表明，对于最大程度地减少（或最大化）两个超模块函数比率的问题，如果两个超模块化函数都是单调的非降低或不增加的，则可以通过查询的多项式数量来实现无界近似比。
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.
