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.
Article PDF
Similar content being viewed by others
Use our pre-submission checklist
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Onn, S., Rothblum, U. Convex Combinatorial Optimization. Discrete Comput Geom 32, 549–566 (2004). https://doi.org/10.1007/s00454-004-1138-y
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-004-1138-y