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

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

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)

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

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)