Research map / Learning theory and algorithms / Combinatorial and search optimization
Decomposable Submodular Function Minimization via Maximum Flow
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Reduce parametric decomposable submodular minimization to maximum-flow calls | Decomposable submodular minimization with small component supports · Parametric decomposable submodular minimization, |V_i| = O(1) | running time: \widetilde{O}\left( \tmf(n, n+r)\log \frac{1}{\epsilon}\right) | Helped |
| Use the proposed maximum-flow reduction instead of prior decomposable minimization algorithms | Decomposable submodular minimization with small component supports · Decomposable submodular minimization | running time: \widetilde{O}(\min\{n^2, nr\} \log^{O(1)}(1/\epsilon)) | Helped |
| Use the maximum-flow-oracle reduction for parametric cuts | Parametric minimum s,t-cut · Parametric min s,t-cut | running time: O(\tmf(n,m\log{n})\cdot\log{\frac{R}{\varepsilon}}\cdot \log{n}) | Helped |
| Apply the reduction on graph minors | Parametric minimum s,t-cut · Planar graphs with linear capacity functions and real coefficients | running time: \tilde{O}(n^{1.21875}) | Helped |
Closest papers by meaning
- Decomposable Submodular Function Minimization: Discrete and Continuous (NeurIPS 2017 · similarity 0.93)
- Fast Decomposable Submodular Function Minimization using Constrained Total Variation (NeurIPS 2019 · similarity 0.92)
- Submodular Function Maximization Over Graphs via Zero-Suppressed Binary Decision Diagrams (AAAI 2018 · similarity 0.91)
- Quadratic Decomposable Submodular Function Minimization (NeurIPS 2018 · similarity 0.90)
- Corporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems (NeurIPS 2025 · similarity 0.88)
- Discrete and Continuous Difference of Submodular Minimization (ICML 2025 · similarity 0.88)
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.