A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions

By Satoru Iwata, Lisa Fleischer, Satoru Fujishige. Symposium on the Theory of Computing, 2000

697 citations recorded by the source corpus.

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grotschel, Lov asz, and Schrijver. The algorithm employs a scaling scheme that uses a ow in the complete directed graph on the underlying set with each arc capacity equal to the scaled parameter. The resulting algorithm runs in time bounded by a polyno- mial in the size of the underlying set and the length of the largest absolute function value. The paper also presents a strongly polynomial version in which the number of steps is bounded by a polynomial in the size of the underlying set, independent of the function values.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/ff63363f50d0cb07d6097bbfcb3ca78612cfaa54

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Optimal approximation for the submodular welfare problem in the value oracle model (2008, background): “Unlike minimization of submodular functions which can be done in polynomial time [10, 23], problems involving submodular maximization are typically NP-hard.”
A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization (2015, methodology): “Our ability to derive the new information hinges on a significant extension of IFF techniques.”
A multi-commodity supply chain design problem (2005, methodology): “The resulting problem (P′′′(j)) can still be expressed as a submodular function minimization problem, and can be polynomially solved using the algorithm proposed by Iwata et al. (2001) that runs in O(m7 log m) time, where m = nL.”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “Submodular functions with Boolean variables can be minimized in polynomial time [69], [70] and for submodular functions on distributive lattices, even strongly polynomial algorithms exist [71], [72].”
A Maximal Tractable Class of Soft Constraints (2003, methodology): “Because our algorithm is specially devised for submodular functions that are expressed as a combination of binary functions, it is much more efficient in this case than existing general algorithms for submodular function minimization (Schrijver, 2000; Iwata et al., 2001 ).”
Stochastic Transportation-Inventory Network Design Problem (2005, background): “Although they proved that the general pricing problem is a submodular function minimization problem that can be readily solved in polynomial time (see, for example, Grotschel et al. 1981, Schrijver 2000, Iwata et al. 2001 ), preliminary computational evidence shows that these algorithms are still n”
A faster strongly polynomial time algorithm for submodular function minimization (2007, methodology): “The running times of the algorithms of Schrijver [13] and Iwata, Fleischer, and Fujishige [10] were shown to be O(n(8) EO + n(9)).”
What energy functions can be minimized via graph cuts? (2002, methodology): “For example, the algorithm of [23] runs in Oðn(5) minflognM;n(2) logngÞ time, where M is an upper bound on jgðXÞj among X 2 2S .”
Non-monotone submodular maximization under matroid and knapsack constraints (2009, background): “Other than many heuristics that have been developed for optimizing these functions [20, 21, 27, 43, 31], many exact and constant-factor approximation algorithms are also known for this problem [38, 39, 44, 26, 15, 48, 18].”
GROSS SUBSTITUTES CONDITION AND DISCRETE CONCAVITY FOR MULTI-UNIT VALUATIONS: A SURVEY (2015, background): “, [20, 39]) can be applied to find such X in Step 1.”
The stochastic location model with risk pooling (2007, neutral): “We relax constraints (3) with Lagrange multipliers λis to obtain the following Lagrangian problem: (SLR) max λ≥0 Lλ = min X,Y ∑ s∈S ∑ j∈J qs fjXj + ∑ i∈I d̂ijsYijs + K̂js √∑ i∈I µisYijs + ∑ s∈S ∑ i∈I λis 1− ∑ j∈J Yijs = ∑ s∈S ∑ j∈J qsfjXj + ∑ i∈I (qsd̂ijs − λis)Yijs + qsK̂js √∑ i∈I µisYijs”