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

We consider the following question: given a submodular/supermodular set function f: 2V R, how should one minimize/maximize its average value f(S)/|S| over non-empty subsets S V? This problem generalizes several well-known objectives, including Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications [42, 34], we formalize two new broad problems: the Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), both of which allow negative and non-monotone functions. Using classical results, we show that DSS, SFM, USSS, UDSS, and Minimum Norm Point (MNP) are all equivalent under strongly polynomial-time reductions. This equivalence enables algorithmic cross-over: methods designed for one problem can be repurposed to solve others efficiently. In particular, we use the perspective of the minimum norm point in the base polyhedron of a sub/supermodular function, which, via Fujishige's results, yields the dense decomposition as a byproduct.