dc.contributor.authorDeza, Antoine.
dc.contributor.authorFukuda, Komei.
dc.contributor.authorPasechnik, Dmitrii V.
dc.contributor.authorSato, Masanori.
dc.identifier.citationDeza, A., Fukuda, K., Pasechnik, D. V., & Sato, M. (2001). On the skeleton of the metric polytope. Discrete and Computational Geometry, 2098, 125-136.en_US
dc.description.abstractWe 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.en_US
dc.relation.ispartofseriesDiscrete and computational geometryen_US
dc.rights© 2001 Springer. This is the author created version of a work that has been peer reviewed and accepted for publication by Discrete and Computational Geometry, Springer. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [https://dx.doi.org/10.1007/3-540-47738-1_10].en_US
dc.titleOn the skeleton of the metric polytopeen_US
dc.typeJournal Article
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen_US
dc.description.versionAccepted versionen_US

Files in this item


This item appears in the following Collection(s)

Show simple item record