A framework of discrete DC programming by discrete convex analysis

DOI10.1007/s10107-014-0792-yzbMath1327.90264OpenAlexW2080412728MaRDI QIDQ494333

Kazuo Murota, Takanori Maehara

Publication date: 31 August 2015

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

Full work available at URL: https://doi.org/10.1007/s10107-014-0792-y

Mathematics Subject Classification ID

Optimality conditions and duality in mathematical programming (90C46) Combinatorial optimization (90C27)

Related Items

Recent progress on integrally convex functions, MAP inference algorithms without approximation for collective graphical models on path graphs via discrete difference of convex algorithm, Strong substitutes: structural properties, and a new algorithm for competitive equilibrium prices, Continuous Relaxation for Discrete DC Programming, Maximize a monotone function with a generic submodularity ratio, A new approach for solving mixed integer DC programs using a continuous relaxation with no integrality gap and smoothing techniques, Continuous relaxation for discrete DC programming, Solving the degree-concentrated fault-tolerant spanning subgraph problem by DC programming, Parametric monotone function maximization with matroid constraints, The complexity of minimizing the difference of two \(M^{\natural}\)-convex set functions, Fast algorithms for maximizing monotone nonsubmodular functions, Fast algorithms for maximizing monotone nonsubmodular functions, Novel algorithms for maximum DS decomposition, Integrality of subgradients and biconjugates of integrally convex functions, Set function optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On functions representable as a difference of convex functions
• Nonlinear discrete optimization. An algorithmic theory
• A faster strongly polynomial time algorithm for submodular function minimization
• New algorithms for convex cost tension problem with application to computer vision
• Generalized polymatroids and submodular flows
• Valuated matroids
• A duality principle for non-convex optimisation and the calculus of variations
• Discrete convex analysis
• Matroid valuation on independent sets
• Convex analysis approach to d. c. programming: Theory, algorithms and applications
• Notes on L-/M-convex functions and the separation theorems
• \(M\)-convex functions and tree metrics
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• DC programming: overview.
• Dijkstra's algorithm and L-concave function maximization
• Submodular containment is hard, even for networks
• Submodular functions and optimization.
• M-Convex Function on Generalized Polymatroid
• ON DISCRETE HESSIAN MATRIX AND CONVEX EXTENSIBILITY
• Recent Developments in Discrete Convex Analysis
• Maximizing Non-monotone Submodular Functions
• On difference convexity of locally Lipschitz functions
• Maximizing a Monotone Submodular Function Subject to a Matroid Constraint
• Global minimization of a difference of two convex functions
• Minimizing a Submodular Function on a Lattice
• A Fenchel-Rockafellar type duality theorem for maximization
• The Concave-Convex Procedure
• Discrete Convex Analysis
• Valuated Matroid Intersection I: Optimality Criteria
• Valuated Matroid Intersection II: Algorithms
• Non-monotone submodular maximization under matroid and knapsack constraints
• On Minimizing Nonseparable Functions Defined on the Integers with an Inventory Application
• Matrices and matroids for systems analysis