# Minimizing a sum of submodular functions

@article{Kolmogorov2012MinimizingAS, title={Minimizing a sum of submodular functions}, author={Vladimir Kolmogorov}, journal={Discret. Appl. Math.}, year={2012}, volume={160}, pages={2246-2258} }

We consider the problem of minimizing a function represented as a sum of submodular terms. We assume each term allows an efficient computation of exchange capacities. This holds, for example, for terms depending on a small number of variables, or for certain cardinality-dependent terms. A naive application of submodular minimization algorithms would not exploit the existence of specialized exchange capacity subroutines for individual terms. To overcome this, we cast the problem as a submodular… Expand

#### Figures and Topics from this paper

#### 58 Citations

Decomposable Submodular Function Minimization via Maximum Flow

- Computer Science
- ICML
- 2021

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… Expand

Active-set Methods for Submodular Minimization Problems

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2017

A new active-set algorithm for total variation denoising with the assumption of an oracle that solves the corresponding SFM problem is proposed, which performs local descent over ordered partitions and its ability to warm start considerably improves the performance of the algorithm. Expand

Fast Decomposable Submodular Function Minimization using Constrained Total Variation

- Mathematics, Computer Science
- NeurIPS
- 2019

A modified convex problem requiring constrained version of the total variation oracles that can be solved with significantly fewer calls to the simple minimization oracles is considered. Expand

Submodular functions: from discrete to continuous domains

- Computer Science, Mathematics
- Math. Program.
- 2019

This paper shows that most results relating submodularity and convexity for set-functions can be extended to all submodular functions, and provides practical algorithms which are based on function evaluations, to minimize generic sub modular functions on discrete domains, with associated convergence rates. Expand

On the Convergence Rate of Decomposable Submodular Function Minimization

- Computer Science, Mathematics
- NIPS
- 2014

It is shown that the algorithm converges linearly, and the upper and lower bounds on the rate of convergence are provided, which relies on the geometry of submodular polyhedra and draws on results from spectral graph theory. Expand

Non-expressibility of Submodular Languages

- Computer Science
- 2012

A negative answer to this question is shown: there are submodular functions that cannot be reduced to the minimum cut problem via the expressibility reduction. Expand

Efficient Minimization of Higher Order Submodular Functions using Monotonic Boolean Functions

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2017

Novel mapping is defined that transform submodular functions of order $k$ into quadratic ones, which can be efficiently minimized in $O(n^3)$ time using a max-flow algorithm. Expand

Distributed Submodular Minimization via Block-Wise Updates and Communications

- Computer Science, Mathematics
- ArXiv
- 2019

A distributed algorithm is proposed in which agents resort to the Lov\`{a}sz extension of their local submodular functions and perform local updates and communications in terms of single blocks of the entire optimization variable, resulting in a reduced computational burden. Expand

Learning with Submodular Functions: A Convex Optimization Perspective

- Computer Science, Mathematics
- Found. Trends Mach. Learn.
- 2013

In Learning with Submodular Functions: A Convex Optimization Perspective, the theory of submodular functions is presented in a self-contained way from a convex analysis perspective, presenting tight links between certain polyhedra, combinatorial optimization and convex optimization problems. Expand

Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions

- Computer Science
- ICML
- 2015

This paper uses random coordinate descent methods to obtain algorithms with faster linear convergence rates and cheaper iteration costs, and their algorithms converge in significantly fewer iterations. Expand

#### References

SHOWING 1-10 OF 39 REFERENCES

Minimizing a Submodular Function Arising From a Concave Function

- Computer Science, Mathematics
- Discret. Appl. Math.
- 1999

As an application of the parametric approach, this work improves the time complexity of a capacity scaling algorithm for the submodular flow problem and discusses a generalization and its relation to the principal partition or the lexicographically optimal base of a sub modular system. Expand

Efficient Minimization of Decomposable Submodular Functions

- Computer Science, Mathematics
- NIPS
- 2010

This paper develops an algorithm, SLG, that can efficiently minimize decomposable submodular functions with tens of thousands of variables, and applies it to synthetic benchmarks and a joint classification-and-segmentation task, and shows that it outperforms the state-of-the-art general purpose sub modular minimization algorithms by several orders of magnitude. Expand

Minimizing symmetric submodular functions

- Mathematics, Computer Science
- Math. Program.
- 1998

We describe a purely combinatorial algorithm which, given a submodular set functionf on a finite setV, finds a nontrivial subsetA ofV minimizingf[A] + f[V ∖ A]. This algorithm, an extension of the… Expand

A simple combinatorial algorithm for submodular function minimization

- Computer Science
- SODA
- 2009

This is the first fully combinatorial submodular function minimization algorithm that does not rely on the scaling method and can be implemented in strongly polynomial time using only additions, subtractions, comparisons, and the oracle calls for function evaluation. Expand

New algorithms for the intersection problem of submodular systems

- Mathematics
- 1992

We consider the problem of finding a maximum common subbase of two submodular systems onE with |E|=n. First, we present a new algorithm by finding the shortest augmenting paths, which begins with a… Expand

Minimization of Locally Defined Submodular Functions by Optimal Soft Arc Consistency

- Mathematics, Computer Science
- Constraints
- 2007

It is proved that every valued constraint satisfaction problem with submodular cost functions has an equivalent instance on the same constraint scopes in which the actual minimum value of the objective function is rendered explicit. Expand

A FASTER SCALING ALGORITHM FOR MINIMIZING SUBMODULAR FUNCTIONS∗

- 2001

Combinatorial strongly polynomial algorithms for minimizing submodular functions have been developed by Iwata, Fleischer, and Fujishige (IFF) and by Schrijver. The IFF algorithm employs a scaling… Expand

A faster strongly polynomial time algorithm for submodular function minimization

- Mathematics, Computer Science
- Math. Program.
- 2009

A combinatorial algorithm that runs in O(n5EO + n6) time, where EO is the time to evaluate f(S) for some submodular function f defined on a set V with n elements is given. Expand

Classes of submodular constraints expressible by graph cuts

- Mathematics, Computer Science
- Constraints
- 2009

Several broad classes of submodular constraints over a Boolean domain are identified which can be minimised in cubic time, and how these results translate to certain optimisation problems arising in computer vision is described. Expand

The expressive power of binary submodular functions

- Mathematics, Computer Science
- Discret. Appl. Math.
- 2009

The results imply limitations on this kind of reduction and establish, for the first time, that it cannot be used in general to minimise arbitrary submodular functions. Expand