Convex combinatorial optimization

DOI10.1007/S00454-004-1138-YMaRDI QIDQ1764165zbMATH OpenOpenAlexFDO

Authors Shmuel Onn, Uriel G. Rothblum

Publication date 23 February 2005

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0309083

Mathematics Subject Classification ID

Convex programming (90C25) Combinatorial optimization (90C27) Polytopes and polyhedra (52B99)

Abstract: We introduce the convex combinatorial optimization problem, a far reaching generalization of the standard linear combinatorial optimization problem. We show that it is strongly polynomial time solvable over any edge-guaranteed family, and discuss several applications.

Recommendations

• Convex discrete optimization
• Polyhedral combinatorics and combinatorial optimization
• Recent trends in combinatorial optimization
• Convex Matroid Optimization
• scientific article; zbMATH DE number 912372

Cited in

(33)

• Graver basis and proximity techniques for block-structured separable convex integer minimization problems
• Zonotopes and the LP-Newton method
• On the largest convex subsets in Minkowski sums
• The use of edge-directions and linear programming to enumerate vertices
• \(N\)-fold integer programming
• Polyhedral results for a class of cardinality constrained submodular minimization problems
• Efficient solutions for weight-balanced partitioning problems
• Primitive zonotopes
• The partition bargaining problem
• A note on the minimum number of edge-directions of a convex polytope
• Optimality conditions for maximizing a function over a polyhedron
• The convex dimension of hypergraphs and the hypersimplicial Van Kampen-Flores theorem
• Graphs of transportation polytopes
• The theory of convex extensions in combinatorial optimization problems
• scientific article; zbMATH DE number 2084778 (Why is no real title available?)
• Convex Matroid Optimization
• Parametric nonlinear discrete optimization over well-described sets and matroid intersections
• Drawing graphs with vertices and edges in convex position
• Minimizing a Low-Dimensional Convex Function Over a High-Dimensional Cube
• scientific article; zbMATH DE number 5888310 (Why is no real title available?)
• A polytope approach to the optimal assembly problem
• Convex integer optimization by constantly many linear counterparts
• The complexity of vector partition
• Efficient edge-skeleton computation for polytopes defined by oracles
• The convex dimension of a graph
• Nonlinear bipartite matching
• Edge-directions of standard polyhedra with applications to network flows
• Convex integer maximization via Graver bases
• On nonlinear multi-covering problems
• Composite convex programs
• The vertices of primitive zonotopes
• An efficient tree decomposition method for permanents and mixed discriminants
• Convex discrete optimization

This page was built for publication: Convex combinatorial optimization

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