A Faster Strongly Polynomial Time Algorithm for Submodular Function Minimization

DOI10.1007/978-3-540-72792-7_19zbMATH Open1136.90459OpenAlexW1886770168MaRDI QIDQ5429271FDOQ5429271

Authors: 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

Recommendations

• A faster strongly polynomial time algorithm for submodular function minimization
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A strongly polynomial time algorithm for a constrained submodular optimization problem
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• scientific article; zbMATH DE number 2086909
• Fast algorithms for maximizing submodular functions
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• scientific article; zbMATH DE number 2119755

Mathematics Subject Classification ID

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

Cited In (17)

• Structural and algorithmic properties for parametric minimum cuts
• Subquadratic submodular function minimization
• Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization
• A polynomial time algorithm for finding a minimum 4-partition of a submodular function
• A faster strongly polynomial time algorithm for submodular function minimization
• Submodular function minimization under a submodular set covering constraint
• Computational geometric approach to submodular function minimization for multiclass queueing systems
• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Theory of principal partitions revisited
• Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost
• Posimodular function optimization
• Posimodular function optimization
• Computational Geometric Approach to Submodular Function Minimization for Multiclass Queueing Systems
• On submodular function minimization
• A tight analysis of the submodular-supermodular procedure
• On the complexity of submodular function minimisation on diamonds
• 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

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