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

DOI10.1145/335305.335317zbMath1296.90104arXivmath/0004089OpenAlexW1976802195WikidataQ62111282 ScholiaQ62111282MaRDI QIDQ3191976

Satoru Fujishige, Satoru Iwata, Lisa K. Fleischer

Publication date: 26 September 2014

Published in: Journal of the ACM, Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Abstract: This paper presents the first combinatorial polynomial-time algorithm for minimizing submodular set functions, answering an open question posed in 1981 by Grotschel, Lovasz, and Schrijver. The algorithm employs a scaling scheme that uses a flow 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 polynomial in the size of the underlying set and the largest length of the function value. The paper also presents a strongly polynomial-time version that runs in time bounded by a polynomial in the size of the underlying set independent of the function value.

Full work available at URL: https://arxiv.org/abs/math/0004089

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (only showing first 100 items - show all)

A 3/2-Approximation for the Metric Many-Visits Path TSP ⋮ Some Results about the Contractions and the Pendant Pairs of a Submodular System ⋮ Robust Monotone Submodular Function Maximization ⋮ Quantum machine learning: a classical perspective ⋮ Decomposition Algorithm for the Single Machine Scheduling Polytope ⋮ Submodular Functions: Learnability, Structure, and Optimization ⋮ Unnamed Item ⋮ Finding a Stable Allocation in Polymatroid Intersection ⋮ Hypergraph Cuts with General Splitting Functions ⋮ Algorithms for maximizing monotone submodular function minus modular function under noise ⋮ Optimal hierarchical clustering on a graph ⋮ ON THE COMPLEXITY OF THE WHITEHEAD MINIMIZATION PROBLEM ⋮ Distributed strategy selection: a submodular set function maximization approach ⋮ Strong valid inequalities for a class of concave submodular minimization problems under cardinality constraints ⋮ The Mixed Evacuation Problem ⋮ Unnamed Item ⋮ Constraint generation approaches for submodular function maximization leveraging graph properties ⋮ On optimization problems in acyclic hypergraphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Theory of Principal Partitions Revisited ⋮ Graphic Submodular Function Minimization: A Graphic Approach and Applications ⋮ The Expressive Power of Valued Constraints: Hierarchies and Collapses ⋮ Binarisation for Valued Constraint Satisfaction Problems ⋮ The fundamental theorem of linear programming: extensions and applications ⋮ Continuous limits of discrete perimeters ⋮ Submodular Function Minimization under a Submodular Set Covering Constraint ⋮ Unnamed Item ⋮ Efficient, optimal stochastic-action selection when limited by an action budget ⋮ Discrete convexity and polynomial solvability in minimum 0-extension problems ⋮ Minimization problems with non-submodular cover constraint ⋮ Computing with Tangles ⋮ Regularized nonmonotone submodular maximization ⋮ Minimizing convex functions with rational minimizers ⋮ Geometric Rescaling Algorithms for Submodular Function Minimization ⋮ DR-submodular function maximization with adaptive stepsize ⋮ Approximate Modularity Revisited ⋮ Finding Submodularity Hidden in Symmetric Difference ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ Half-integrality, LP-branching, and FPT Algorithms ⋮ ON THE PIPAGE ROUNDING ALGORITHM FOR SUBMODULAR FUNCTION MAXIMIZATION — A VIEW FROM DISCRETE CONVEX ANALYSIS ⋮ Linear Time Algorithms for Happy Vertex Coloring Problems for Trees ⋮ Covering Intersecting Bi-set Families under Matroid Constraints ⋮ Inferring Relative Ability from Winning Probability in Multientrant Contests ⋮ On a General Framework for Network Representability in Discrete Optimization ⋮ Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms ⋮ Digraphs of Bounded Width ⋮ Introduction to the Maximum Solution Problem ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Improved Randomized Algorithm for k-Submodular Function Maximization ⋮ Tight Approximation for Unconstrained XOS Maximization ⋮ A Polynomial Algorithm for a Class of 0–1 Fractional Programming Problems Involving Composite Functions, with an Application to Additive Clustering ⋮ Approximation algorithms for submodular vertex cover problems with linear/submodular penalties using primal-dual technique ⋮ Realizing symmetric set functions as hypergraph cut capacity ⋮ On a general framework for network representability in discrete optimization ⋮ The mixed evacuation problem ⋮ Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications ⋮ A new greedy strategy for maximizing monotone submodular function under a cardinality constraint ⋮ On total variation minimization and surface evolution using parametric maximum flows ⋮ Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ Minimum degree orderings ⋮ Efficient implementation of Carathéodory's theorem for the single machine scheduling polytope ⋮ Image restoration with discrete constrained total variation. II: Levelable functions, convex priors and non-convex cases ⋮ Separation of partition inequalities with terminals ⋮ Supermodular functions and the complexity of MAX CSP ⋮ Maximizing a non-decreasing non-submodular function subject to various types of constraints ⋮ An \(O(n \log^2 n)\) algorithm for the optimal sink location problem in dynamic tree networks ⋮ Optimal allocation of stock levels and stochastic customer demands to a capacitated resource ⋮ The stochastic location model with risk pooling ⋮ Reachability in arborescence packings ⋮ Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Rank-width: algorithmic and structural results ⋮ Effective divisor classes on metric graphs ⋮ Every finite distributive lattice is isomorphic to the minimizer set of an \(M^\natural \)-concave set function ⋮ Testing branch-width ⋮ Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Computational geometric approach to submodular function minimization for multiclass queueing systems ⋮ Equivalence of convex minimization problems over base polytopes ⋮ FPT approximation schemes for maximizing submodular functions ⋮ Submodular functions: from discrete to continuous domains ⋮ Streaming algorithm for maximizing a monotone non-submodular function under \(d\)-knapsack constraint ⋮ Maximizing non-monotone submodular set functions subject to different constraints: combined algorithms ⋮ The \(b\)-branching problem in digraphs ⋮ Improved bound for the Carathéodory rank of the bases of a matroid ⋮ A note on Schrijver's submodular function minimization algorithm. ⋮ A strongly polynomial algorithm for line search in submodular polyhedra ⋮ A push-relabel framework for submodular function minimization and applications to parametric optimization ⋮ A note on the minimization of symmetric and general submodular functions ⋮ Build-pack planning for hard disk drive assembly with approved vendor matrices and stochastic demands ⋮ Fast scaling algorithms for M-convex function minimization with application to the resource allocation problem. ⋮ Stochastic block-coordinate gradient projection algorithms for submodular maximization ⋮ Is submodularity testable? ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ On the complexity of submodular function minimisation on diamonds ⋮ Hypertree width and related hypergraph invariants ⋮ Complexity of the cluster deletion problem on subclasses of chordal graphs ⋮ Partitioning posets

This page was built for publication: A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions