An exponential value-oracle lower bound for k-submodular function minimization

DOI10.1137/26M1889795MaRDI QIDQ7356629zbMATH OpenFDO

Authors Yuichi Yoshida

Publication date 24 September 2026

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/26M1889795

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• A combinatorial strongly polynomial algorithm for minimizing submodular functions
• Bisubmodular Function Minimization
• Improved approximation algorithms for \(k\)-submodular function maximization
• Maximizing k-submodular functions and beyond
• On \(k\)-submodular relaxation
• The power of linear programming for valued CSPs
• Towards minimizing k-submodular functions

This page was built for publication: An exponential value-oracle lower bound for \(k\)-submodular function minimization

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