The complexity of minimizing the difference of two \(M^{\natural}\)-convex set functions

DOI10.1016/j.orl.2015.08.011zbMath1408.90243OpenAlexW1236105380MaRDI QIDQ1785434

Yusuke Kobayashi

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2015.08.011

zbMATH Keywords

matroidNP-hardnessDC programming\(M^{\natural}\)-convex set functions

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices ⋮ Continuous relaxation for discrete DC programming

Cites Work

• Unnamed Item
• A framework of discrete DC programming by discrete convex analysis
• Valuated matroids
• Submodular functions and optimization.
• M-Convex Function on Generalized Polymatroid

This page was built for publication: The complexity of minimizing the difference of two \(M^{\natural}\)-convex set functions