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 : 2 V → 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. Through this perspective, we show that a recent converging heuristic for DSS, SUPERGREEDY++ [17,32], and Wolfe's minimum norm point algorithm are both universal solvers for all of these problems.

On the theoretical front, we explain the observation made in recent work [42,34] that SUPERGREEDY++ appears to work well even in settings beyond DSS. Surprisingly, we also show that this simple algorithm can be used for Submodular Function Minimization, including acting as a practical minimum s-t cut algorithm.

On the empirical front, we explore the utility of several algorithms for recent problems. We conduct over 400 experiments across seven problem types and largescale synthetic and real-world datasets (up to ≈ 100 million edges). Our results reveal that methods historically considered inefficient, such as convex-programming methods, flow-based solvers, and Fujishige-Wolfe's algorithm, outperform stateof-the-art task-specific baselines by orders of magnitude on concrete problems like HNSN [42]. These findings challenge prevailing assumptions and demonstrate that with the proper framing, general optimization algorithms can be both scalable and state-of-the-art for supermodular and submodular ratio problems.

39th Conference on Neural Information Processing Systems (NeurIPS 2025).