On the volume of the elliptope and related metric polytopes
For researchers in combinatorial optimization, this work provides volume-based comparisons of polynomial-time relaxations of the cut polytope, offering global bounds beyond worst-case ratios.
This paper studies the volumes of the cut polytope, metric polytope, rooted metric polytope, and elliptope on graphs with n vertices. It shows that for the complete graph, the rooted metric polytope has much larger volume than the elliptope, while for the metric polytope, volume comparisons depend on n, with exact formulas provided for sparse graphs.
In this paper, we investigate the relationships between the volumes of four convex bodies: the cut polytope, metric polytope, rooted metric polytope, and elliptope, defined on graphs with $n$ vertices. The cut polytope is contained in each of the other three, which, for optimization purposes, provide polynomial-time relaxations. It is therefore of interest to see how tight these relaxations are. Worst-case ratio bounds are well known, but these are limited to objective functions with non-negative coefficients. Volume ratios, pioneered by Jon Lee with several co-authors, give global bounds and are the subject of this paper. For the rooted metric polytope over the complete graph, we show that its volume is much greater than that of the elliptope. For the metric polytope, for small values of $n$, we show that its volume is smaller than that of the elliptope; however, for large values, volume estimates suggest the converse is true. We also give exact formulae for the volume of the cut polytope for some families of sparse graphs.