Abstract:

We introduce and study the convex combinatorial optimization problem, a broad generalization of standard linear combinatorial optimization over implicitly presented 0-1 polytopes. We show that it is strongly polynomial time solvable over any edge-well-behaved family, providing a unified framework which captures various applications such as to matroids, clustering, and quadratic assignment. Convex combinatorial optimization opens up many new lines of research, including the combinatorial-geometric classification of edge-well-behaved families and the study of various relaxations, bounds, and approximations.