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

arXiv: https://arxiv.org/abs/2505.17443 · HTML: https://mlsanity.com/paper/2505.17443/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 60 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 13 of 13)

- [Near-optimal Approximate Discrete and Continuous Submodular Function Minimization](https://mlsanity.com/paper/1909.00171/) (2019)
- [Provable Submodular Minimization using Wolfe's Algorithm](https://mlsanity.com/paper/1411.0095/) (2014)
- [Densest Subgraph in Dynamic Graph Streams](https://mlsanity.com/paper/1506.04417/) (2015)
- [Subquadratic Submodular Function Minimization](https://mlsanity.com/paper/1610.09800/) (2016)
- [The Generalized Mean Densest Subgraph Problem](https://mlsanity.com/paper/2106.00909/) (2021)
- [Online Dense Subgraph Discovery via Blurred-Graph Feedback](https://mlsanity.com/paper/2006.13642/) (2020)
- [Faster width-dependent algorithm for mixed packing and covering LPs](https://mlsanity.com/paper/1909.12387/) (2019)
- [Minimizing Convex Functions with Rational Minimizers](https://mlsanity.com/paper/2007.01445/) (2020)
- [Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing](https://mlsanity.com/paper/2305.02987/) (2023)
- [Multiplicative Weights Update, Area Convexity and Random Coordinate Descent for Densest Subgraph Problems](https://mlsanity.com/paper/2405.18809/) (2024)
- [On the Generalized Mean Densest Subgraph Problem: Complexity and Algorithms](https://mlsanity.com/paper/2306.02172/) (2023)
- [Densest Subhypergraph: Negative Supermodular Functions and Strongly Localized Methods](https://mlsanity.com/paper/2310.13792/) (2023)
- [On Deleting Vertices to Reduce Density in Graphs and Supermodular Functions](https://mlsanity.com/paper/2503.08828/) (2025)

## Abstract (arXiv)

We study the problem of minimizing or maximizing the average value  f(S)/|S|  of a submodular or supermodular set function  f: 2V → ℝ  over non-empty subsets  S subseteq V . This generalizes classical problems such as Densest Subgraph (DSG), Densest Supermodular Set (DSS), and Submodular Function Minimization (SFM). Motivated by recent applications, we introduce two broad formulations: Unrestricted Sparsest Submodular Set (USSS) and Unrestricted Densest Supermodular Set (UDSS), which allow for negative and non-monotone functions. We show that DSS, SFM, USSS, UDSS, and the Minimum Norm Point (MNP) problem are equivalent under strongly polynomial-time reductions, enabling algorithmic crossover. In particular, viewing these through the lens of the MNP in the base polyhedron, we connect Fujishige's theory with dense decomposition, and show that both Fujishige-Wolfe's algorithm and the heuristic textscSuperGreedy++ act as universal solvers for all these problems, including sub-modular function minimization. Theoretically, we explain why textscSuperGreedy++ is effective beyond DSS, including for tasks like submodular minimization and minimum  s - t  cut. Empirically, we test several solvers, including the Fujishige-Wolfe algorithm on over 400 experiments across seven problem types and large-scale real/synthetic datasets. Surprisingly, general-purpose convex and flow-based methods outperform task-specific baselines, demonstrating that with the right framing, general optimization techniques can be both scalable and state-of-the-art for submodular and supermodular ratio problems.