A fully combinatorial algorithm for submodular function minimization.

DOI10.1006/JCTB.2001.2072zbMATH Open1175.90332OpenAlexW2585238812MaRDI QIDQ1850585FDOQ1850585

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

Recommendations

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• scientific article; zbMATH DE number 7051294
• A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions
• Publication:4886038
• Minimizing symmetric submodular functions

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (17)

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

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)