On the skeleton of the metric polytope

• Main Authors: Deza, Antoine., Fukuda, Komei., Pasechnik, Dmitrii V., Sato, Masanori.
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2014
• Subjects: DRNTU::Science::Physics
• Online Access: https://hdl.handle.net/10356/102099; http://hdl.handle.net/10220/18804
• Institution: Nanyang Technological University

We consider convex polyhedra with applications to well-known combinatorial optimization problems: the metric polytope m n and its relatives. For n ≤ 6 the description of the metric polytope is easy as m n has at most 544 vertices partitioned into 3 orbits; m 7 - the largest previously known instance - has 275 840 vertices but only 13 orbits. Using its large symmetry group, we enumerate orbitwise 1 550 825 600 vertices of the 28-dimensional metric polytope m s . The description consists of 533 orbits and is conjectured to be complete. The orbitwise incidence and adjacency relations are also given. The skeleton of m s could be large enough to reveal some general features of the metric polytope on n nodes. While the extreme connectivity of the cuts appears to be one of the main features of the skeleton of m n , we conjecture that the cut vertices do not form a cut-set. The combinatorial and computational applications of this conjecture are studied. In particular, a heuristic skipping the highest degeneracy is presented.