Home
Scholarly Works
The Ridge Graph of the Metric Polytope and Some...
Conference

The Ridge Graph of the Metric Polytope and Some Relatives

Abstract

The metric polytope is a $$\left( {\begin{array}{*{20}c} n \\ 2 \\ \end{array}} \right) $$ -dimensional convex polytope defined by its 4 $$\left( {\begin{array}{*{20}c} n \\ 3 \\ \end{array}} \right) $$ facets. The vertices of the metric polytope are known only up to n = 6, for n = 7 they number more than 60 000. The study of the metric polytope and its relatives (the metric cone, the cut polytope and the cut cone) is mainly motivated by their application to the maximum cut and multicommodity flow feasibility problems. We characterize the ridge graph of the metric polytope, i.e. the edge graph of its dual, and, as corollary, obtain that the diameter of the dual metric polytope is 2. For n ≥ 5, the edge graph of the metric polytope restricted to its integral vertices called cuts, and to some $$\left\{ {\frac{1}{3},\,\frac{2}{3}} \right\} $$ -valued vertices called anticuts, is, besides the clique on the cuts, the bipartite double of the complement of the folded n-cube. We also give similar results for the metric cone, the cut polytope and the cut cone.

Authors

Deza A; Deza M

Pagination

pp. 359-372

Publisher

Springer Nature

Publication Date

January 1, 1994

DOI

10.1007/978-94-011-0924-6_16

Conference proceedings

Nato Science Series C:

ISSN

1389-2185
View published work (Non-McMaster Users)

Contact the Experts team