A combinatorial strongly polynomial algorithm for minimizing submodular functions

DOI10.1145/502090.502096MaRDI QIDQ6829277zbMATH OpenFDO

Authors Satoru Iwata, Lisa Fleischer, Satoru Fujishige

Publication date 11 February 2008

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/502090.502096

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Review text

This paper presents a combinatorial polynomial-time algorithm for minimizing submodular functions, answering an open question posed in 1981 by Grötschel, Lovász, 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 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.

Cited in

(18)

• Linearly representable submodular functions: an algebraic algorithm for minimization
• Approximation algorithms for two extensions of min-k-union
• Minimizing symmetric convex functions over hybrid of continuous and discrete convex sets
• An o( n)-approximation for submodular facility location
• A direct proof of the characterization of the convexity of the discrete Choquet integral
• Approximation algorithm for extracting densest subgraph over matching-like constraints
• A branch-and-cut algorithm for the multiple Steiner TSP with order constraints
• Strongly stable matchings under matroid constraints
• Finding diverse minimum s-t cuts
• On extensions of min-k-union
• Shortest cycles with monotone submodular costs
• Polynomial algorithms to minimize 2/3-submodular functions
• Algorithmic contract theory: a survey
• Weakly polynomial-time algorithms to minimize 2/3-submodular functions
• Practical algorithm for minimum cost submodular cover problem with performance guarantees
• Minimum cost nowhere-zero flows and cut-balanced orientations
• An exponential value-oracle lower bound for k-submodular function minimization
• Finding diverse solutions in combinatorial problems with a distributive lattice structure

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6829277)