A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time

By Alexander Schrijver. 2000

731 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

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

Determinantal Point Processes for Machine Learning (2012, background): “Submodular functions can be minimized in polynomial time [Schrijver, 2000], and many results exist for approximately maximizing monotone submodular functions, which have the special property that supersets always have higher function values than their subsets [Nemhauser et al., 1978, Fisher et al.,…”
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, 44, 31], many exact and constant-factor approximation algorithms are also known for this problem [39, 40, 45, 26, 15, 50, 18].”
Stochastic Transportation-Inventory Network Design Problem (2005, neutral): “(1981), Schrijver (1999), and Iwata et. al.”
A faster strongly polynomial time algorithm for submodular function minimization (2007, methodology): “Otherwise, if f(∅) ≠ 0, we can subtract f(∅) from f(S) for all S ⊆ V. Grotschel, Lovasz, and Schrijver [7] and [8] gave the first polynomial time and strongly polynomial time algorithms for minimizing a submodular function.”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “Submodular functions with Boolean variables can be minimized in polynomial time [67], [68] and, for submodular functions on distributive lattices, even strongly polynomial algorithms exist [69], [70].”
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).”
A Joint Location - Inventory Model (2003, background): “Zheng (1992) has shown that the maximum relative error is bounded by 0.”
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.”
Multi-document Summarization via Budgeted Maximization of Submodular Functions (2010, background): “It has been shown that any submodular function can be minimized in polynomial time (Schrijver, 2000)(Iwata et al.”
Submodular secretary problem and extensions (2010, background): “While the Min Cut problem in graphs is a classical polynomial-time solvable problem, and more generally it has been shown that any submodular function can be minimized in polynomial time [29, 37], maximization turns out to be more difficult and indeed all the aforementioned special cases are NP-hard”
Cosegmentation of Image Pairs by Histogram Matching - Incorporating a Global Constraint into MRFs (2006, background): “It is well-known that any submodular function can be minimized in polynomial time [19].”
Submodular maximization by simulated annealing (2010, background): “This point of view explains why submodular functions can be minimized efficiently [16, 11, 28].”
Advanced Structured Prediction (2014, methodology): “Using a polynomial-time algorithm for minimizing submodular set functions (Schrijver, 2000; Iwata et al., 2001), Cohen et al.”
Pseudo-Boolean optimization (2002, background): “Let us remark /nally that even though the minimum of a submodular (or the maximum of a supermodular) set function can be found in polynomial time [71], or even in strongly polynomial time (see [108,152]), the opposite optimization problems, i.”
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.”