A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

DOI10.1007/978-3-540-72792-7_19zbMath1136.90459OpenAlexW1886770168MaRDI QIDQ5429271

James B. Orlin

Publication date: 29 November 2007

Published in: Integer Programming and Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-72792-7_19

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Combinatorial optimization (90C27)

Related Items (7)

Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Theory of Principal Partitions Revisited ⋮ On the complexity of submodular function minimisation on diamonds ⋮ Structural and algorithmic properties for parametric minimum cuts ⋮ Polyhedral Clinching Auctions and the AdWords Polytope ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency

This page was built for publication: A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization