# Decomposable Submodular Function Minimization via Maximum Flow

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 64 references that are in the map.
- First posted on arXiv 5 Mar 2021.

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

- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization](https://mlsanity.com/paper/1508.04874/) (2015)
- [Reflection methods for user-friendly submodular optimization](https://mlsanity.com/paper/1311.4296/) (2013)
- [Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back](https://mlsanity.com/paper/1307.2205/) (2013)
- [Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao](https://mlsanity.com/paper/2101.07233/) (2021)
- [Computing Maximum Flow with Augmenting Electrical Flows](https://mlsanity.com/paper/1608.06016/) (2016)
- [Subquadratic Submodular Function Minimization](https://mlsanity.com/paper/1610.09800/) (2016)
- [Decomposable Submodular Function Minimization: Discrete and Continuous](https://mlsanity.com/paper/1703.01830/) (2017)
- [Structured learning of sum-of-submodular higher order energy functions](https://mlsanity.com/paper/1309.7512/) (2013)
- [Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions](https://mlsanity.com/paper/1502.02643/) (2015)
- [Revisiting Decomposable Submodular Function Minimization with Incidence Relations](https://mlsanity.com/paper/1803.03851/) (2018)
- [On the Convergence Rate of Decomposable Submodular Function Minimization](https://mlsanity.com/paper/1406.6474/) (2014)
- [Faster Energy Maximization for Faster Maximum Flow](https://mlsanity.com/paper/1910.14276/) (2019)
- [On the Approximation of Submodular Functions](https://mlsanity.com/paper/1304.4948/) (2013)
- [Geometric Rescaling Algorithms for Submodular Function Minimization](https://mlsanity.com/paper/1707.05065/) (2017)
- [Fast Decomposable Submodular Function Minimization using Constrained Total Variation](https://mlsanity.com/paper/1905.11327/) (2019)
- [A Deterministic Parallel APSP Algorithm and its Applications](https://mlsanity.com/paper/2101.02311/) (2021)

## Built on by (most cited first, 3 of 3)

- [Sparsification of Decomposable Submodular Functions](https://mlsanity.com/paper/2201.07289/) (2022)
- [Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components](https://mlsanity.com/paper/2110.14859/) (2021)
- [Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient Oracle Complexity](https://mlsanity.com/paper/2208.03811/) (2022)

## Abstract (arXiv)

This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on O(1) elements of the ground set V and is polynomially bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with O(vert V vert) vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. We solve this minimization problem by lifting the solutions of a parametric cut problem, which we obtain via a new efficient combinatorial reduction to maximum flow. This reduction is of independent interest and implies some previously unknown bounds for the parametric minimum s,t-cut problem in multiple settings.