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

TL;DR

We consider the following question: given a submodular or supermodular set function $f:2^V \to \mathbb{R}$, how should one minimize or maximize its average value $f(S)/\ | S\ | $ over non-empty subsets $S\s…

Opening excerpt from the authors’ abstract. source