The complexity of minimizing the difference of two M^-convex set functions

DOI10.1016/J.ORL.2015.08.011MaRDI QIDQ1785434zbMATH OpenOpenAlexFDO

Authors 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

\(M^{\natural}\)-convex set functionsDC programmingmatroidNP-hardness

Mathematics Subject Classification ID

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

Recommendations

• Submodular function minimization and maximization in discrete convex analysis
• On equivalence of M^-concavity of a set function and submodularity of its conjugate
• A framework of discrete DC programming by discrete convex analysis
• On Steepest Descent Algorithms for Discrete Convex Functions
• Minimizing the product of two discrete convex functions

Cites work

• \(M\)-convex function on generalized polymatroid
• A framework of discrete DC programming by discrete convex analysis
• Submodular function minimization and maximization in discrete convex analysis
• Submodular functions and optimization.
• Valuated matroids

Cited in

(3)

• Continuous relaxation for discrete DC programming
• scientific article; zbMATH DE number 2210595 (Why is no real title available?)
• Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices

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

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