Polynomial algorithms to minimize 2/3-submodular functions

DOI10.1007/978-3-031-59835-7_24MaRDI QIDQ7030550zbMATH OpenFDO

Authors Ryuhei Mizutani, Yuki Yoshida

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-59835-7_24

zbMATH Keywords

2/3-submodular functionpolynomial-time algorithmsupermodular coloring

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial strongly polynomial algorithm for minimizing submodular functions
• A faster cutting plane method and its implications for combinatorial and convex optimization
• A faster strongly polynomial time algorithm for submodular function minimization
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• scientific article; zbMATH DE number 3970767 (Why is no real title available?)
• scientific article; zbMATH DE number 7051294 (Why is no real title available?)
• Matroid Intersection under Restricted Oracles
• On an estimate of the chromatic class of a \(p\)-graph
• Subquadratic submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• Variations for Lovász’ Submodular Ideas

Cited in

(2)

• Supermodular extension of Vizing's edge-coloring theorem
• Weakly polynomial-time algorithms to minimize 2/3-submodular functions

This page was built for publication: Polynomial algorithms to minimize 2/3-submodular functions

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