Improved algorithms for submodular function minimization and submodular flow

DOI10.1145/335305.335318MaRDI QIDQ3191977zbMATH OpenOpenAlexFDO

Authors Lisa Fleischer, Satoru Iwata

Publication date 26 September 2014

Published in Proceedings of the thirty-second annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/335305.335318

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• A Faster Scaling Algorithm for Minimizing Submodular Functions
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• scientific article; zbMATH DE number 7051294
• scientific article; zbMATH DE number 1303553

Cited in

(29)

• Hypergraphic submodular function minimization
• scientific article; zbMATH DE number 3906195 (Why is no real title available?)
• A Primal-Dual Algorithm for Submodular Flows
• A Faster Scaling Algorithm for Minimizing Submodular Functions
• Submodular function minimization
• Submodular function minimization
• Subquadratic submodular function minimization
• Minimizing a sum of submodular functions
• Geometric rescaling algorithms for submodular function minimization
• Exact algorithms for combinatorial optimization problems with submodular objective functions
• A flow model based on polylinking system
• scientific article; zbMATH DE number 3956777 (Why is no real title available?)
• Graphic submodular function minimization: a graphic approach and applications
• A note on Schrijver's submodular function minimization algorithm.
• scientific article; zbMATH DE number 1303553 (Why is no real title available?)
• A faster strongly polynomial time algorithm for submodular function minimization
• A Push/Relabel framework for submodular flows and its definement for 0-1 submodular flows
• A push-relabel framework for submodular function minimization and applications to parametric optimization
• SFO: a toolbox for submodular function optimization
• Geometric rescaling algorithms for submodular function minimization
• A dual algorithm for submodular flow problems
• A note on polylinking flow networks
• A submodular function minimization algorithm based on the minimum-norm base
• Simple push-relabel algorithms for matroids and submodular flows
• The complexity of soft constraint satisfaction
• Submodular function minimization and related topics
• A tight analysis of the submodular-supermodular procedure
• scientific article; zbMATH DE number 2086909 (Why is no real title available?)
• Submodular minimization via pathwidth

This page was built for publication: Improved algorithms for submodular function minimization and submodular flow

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