Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems

Elfarouk Harb, Yousef Yassin, Chandra Chekuri

We study the problem of minimizing or maximizing the average value $f(S)/|S|$ of a submodular or supermodular set function $f:2^V\to \mathbb{R}$ over non-empty subsets $ S \s…