A fully combinatorial algorithm for submodular function minimization.

DOI10.1006/jctb.2001.2072zbMath1175.90332OpenAlexW2585238812MaRDI QIDQ1850585

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)

Related Items (11)

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ A strongly polynomial algorithm for line search in submodular polyhedra ⋮ Theory of Principal Partitions Revisited ⋮ Graphic Submodular Function Minimization: A Graphic Approach and Applications ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ Efficient minimization of higher order submodular functions using monotonic Boolean functions ⋮ The expressive power of binary submodular functions ⋮ Coordinatewise domain scaling algorithm for M-convex function minimization ⋮ Submodular function minimization ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Traveling salesman games with the Monge property

Cites Work

• Unnamed Item
• Unnamed Item
• Testing membership in matroid polyhedra
• A strongly polynomial minimum cost circulation algorithm
• On submodular function minimization
• Generalized polymatroids and submodular flows
• The ellipsoid method and its consequences in combinatorial optimization
• Submodular functions and optimization
• Geometric algorithms and combinatorial optimization
• Minimizing symmetric submodular functions
• A capacity scaling algorithm for convex cost submodular flows
• A faster capacity scaling algorithm for minimum cost submodular flow
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Cores of convex games
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• A NOTE ON SUBMODULAR FUNCTIONS ON DISTRIBUTIVE LATTICES
• A capacity-rounding algorithm for the minimum-cost circulation problem: A dual framework of the Tardos algorithm
• Computing Edge-Connectivity in Multigraphs and Capacitated Graphs

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