Research map / Learning theory and algorithms / Submodular and game algorithms
Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that SFM, DSS, MNP, USSS and UDSS are equivalent under strongly polynomial reductions, that SuperGreedy++ and Fujishige-Wolfe MNP act as universal solvers for them, and runs ~400 experiments showing general solvers beat specialized baselines on HNSN and min s-t cut.
Problem
Minimizing or maximizing the average value f(S)/|S| of sub/supermodular set functions (ratio problems such as HNSN, densest subgraph, anchored densest subgraph), including unrestricted cases where f can be negative or non-monotone, and understanding why SuperGreedy++ works beyond DSS.
Approach
Connects submodular/supermodular ratio problems to the minimum norm point in the base polytope via Lemma (threshold of the min-norm point minimizes f(S)-λ|S|), proves the five problems are equivalent under exact reductions and additive-approximation transfer, and shows SuperGreedy++ and Fujishige-Wolfe are universal solvers through Frank-Wolfe analysis.
Key results
- On HNSN, MNP achieved speedups from 5x to 595x over prior baselines (e.g., on YooChoose).
- SuperGreedy++ found the exact min s-t cut in 16 of 24 instances, otherwise within 1.000023x of optimum within 500 iterations.
- The paper reports over 400 experiments across seven problem types with graphs up to about 100 million edges.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MNP instead of the best previously published baseline | HNSN on YooChoose · HNSN on YooChoose | speedup: 595× | Helped |
| Use MNP or Frank-Wolfe instead of the six prior baselines | HNSN · HNSN datasets | runtime speedup: 5× to 595× | Helped |
| Use SuperGreedy++ instead of exact flow-based methods, MNP, or Frank-Wolfe | Minimum s-t Cut · Minimum s-t Cut instances | time to approximate the minimum cut | Helped |
| Use SuperGreedy++ for up to 500 iterations | Minimum s-t Cut · Minimum s-t Cut instances | approximation ratio to optimum: 1.000023× | Helped |
| Use MNP or Frank-Wolfe instead of SuperGreedy++ | Minimum s-t Cut · Minimum s-t Cut | solver efficiency | Hurt |
| Increase p in the generalized p-mean objective | Frank-Wolfe and MNP · Generalized p-mean Densest Subgraph | performance: p ∈ {1.1, 1.25, 1.5, 1.75} | Helped |
| Increase p in the generalized p-mean objective | SuperGreedy++ · Generalized p-mean Densest Subgraph | performance: p ∈ {1.1, 1.25, 1.5, 1.75} | No clear effect |
| Use Frank-Wolfe or MNP rather than SuperGreedy++ | Generalized p-mean Densest Subgraph · close-cliques | early-stage time to maximum density | Helped |
| Use SuperGreedy++ rather than Frank-Wolfe or MNP | Generalized p-mean Densest Subgraph · Real-world instances | time to converge | Helped |
| Use RCDM, FISTA, or SuperGreedy++ rather than Frank-Wolfe or MNP | Densest Subgraph · Densest Subgraph datasets | convergence to near-optimal density | Helped |
| Use flow-based methods with density improvement rather than convex programming methods | Densest Subgraph · Densest Subgraph datasets | time to exact optimum | Helped |
| Use flow-based methods rather than other approaches | Densest Subgraph · Densest Subgraph datasets | memory usage: 2–3× | Hurt |
Surprising findings
- SuperGreedy++, designed for densest supermodular set, works as an effective minimum s-t cut / SFM algorithm, converging before the exact flow solver on many instances.
- MNP and Frank-Wolfe, which excel on HNSN, underperform on min s-t cut, showing problem structure drives solver efficiency.
Limitations
- Approximation guarantees are additive, and the best-performing method varies by instance, so no single solver dominates.
- Direct problem-specific analysis of SuperGreedy++ for settings like min s-t cut remains open.
- Flow-based methods do not apply to general supermodular objectives such as p-mean densest subgraph.
Experimental setup
Datasets: HNSN benchmark datasets (Ling et al.) DIMACS min-cut instances BVZ-sawtooth min s-t cut instances SNAP densest subgraph graphs (com-amazon, com-dblp, com-orkut, roadNet)
Benchmarks: HNSN datasets (12) min s-t cut DIMACS and BVZ-sawtooth densest subgraph datasets (7) generalized p-mean densest subgraph (5 datasets)
Metrics: wall-clock runtime density / objective value found min-cut value accuracy
Baselines: ContractDecompose Linear programming (Gurobi) GAR GR FGR GRR Edmonds-Karp max-flow FISTA RCDM
Builds on: Greedy++ SuperGreedy++ Frank-Wolfe Fujishige-Wolfe minimum norm point algorithm Dinkelbach method
Closest papers by meaning
- Algorithms for Optimizing the Ratio of Submodular Functions (ICML 2016 · similarity 0.92)
- Greed is Still Good: Maximizing Monotone Submodular+Supermodular (BP) Functions (ICML 2018 · similarity 0.90)
- Online Two-Stage Submodular Maximization (NeurIPS 2025 · similarity 0.89)
- Efficient Submodular Maximization for Sums of Concave over Modular Functions (ICLR 2026 · similarity 0.89)
- An Asymptotically Optimal Approximation Algorithm for Multiobjective Submodular Maximization at Scale (ICML 2025 · similarity 0.88)
- Discrete and Continuous Difference of Submodular Minimization (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.