Weakly polynomial-time algorithms to minimize 2/3-submodular functions

DOI10.1007/S10107-026-02327-3MaRDI QIDQ7239202zbMATH OpenFDO

Authors Ryuhei Mizutani, Yuki Yoshida

Publication date 8 May 2026

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S10107-026-02327-3

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 7051294 (Why is no real title available?)
• scientific article; zbMATH DE number 3422402 (Why is no real title available?)
• Matroid Intersection under Restricted Oracles
• Odd Submodular Functions, Dilworth Functions and Discrete Convex Functions
• On an estimate of the chromatic class of a \(p\)-graph
• Polynomial algorithms to minimize 2/3-submodular functions
• Subquadratic submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• Variations for Lovász’ Submodular Ideas

This page was built for publication: Weakly polynomial-time 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 Q7239202)