A fully combinatorial algorithm for submodular function minimization.

DOI10.1006/JCTB.2001.2072MaRDI QIDQ1850585zbMATH OpenOpenAlexFDO

Authors Satoru Iwata

Publication date 10 December 2002

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.2001.2072

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Combinatorial aspects of matroids and geometric lattices (05B35)

Recommendations

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• scientific article; zbMATH DE number 7051294
• scientific article; zbMATH DE number 910864
• Minimizing symmetric submodular functions

Cites work

• scientific article; zbMATH DE number 3904328 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
• A capacity scaling algorithm for convex cost submodular flows
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A faster capacity scaling algorithm for minimum cost submodular flow
• A strongly polynomial minimum cost circulation algorithm
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
• Cores of convex games
• Generalized polymatroids and submodular flows
• Geometric algorithms and combinatorial optimization
• Minimizing symmetric submodular functions
• On submodular function minimization
• Submodular functions and optimization
• Testing membership in matroid polyhedra
• The ellipsoid method and its consequences in combinatorial optimization

Cited in

(17)

• Coordinatewise domain scaling algorithm for M-convex function minimization
• scientific article; zbMATH DE number 910864 (Why is no real title available?)
• Algorithms for symmetric submodular function minimization under hereditary constraints and generalizations
• The expressive power of binary submodular functions
• scientific article; zbMATH DE number 5319970 (Why is no real title available?)
• Minimization of locally defined submodular functions by optimal soft arc consistency
• Traveling salesman games with the Monge property
• Graphic submodular function minimization: a graphic approach and applications
• A note on Schrijver's submodular function minimization algorithm.
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• scientific article; zbMATH DE number 7051294 (Why is no real title available?)
• Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
• A strongly polynomial algorithm for line search in submodular polyhedra
• Theory of principal partitions revisited
• Efficient minimization of higher order submodular functions using monotonic Boolean functions
• Submodular function minimization

This page was built for publication: A fully combinatorial algorithm for submodular function minimization.

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