An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods

Simple item page
dc.creatorVeomett, Ellen
dc.date2006-10-11
dc.date.accessioned2026-07-07T07:28:59Z
dc.date.available2026-07-07T07:28:59Z
dc.descriptionFor the Traveling Salesman Polytope on n cities T_n, we construct its approximation Q_k, k=1, 2, . . ., n^(1/3) using a projection of a polytope whose number of facets is polynomial in n (of degree linear in k). We show that T_n is contained in Q_k for each k, and that the scaling of Q_k by k/n+O(1/n) is contained in T_n for each k. We show that certain facets of T_n lie on the boundary of Q_k.
dc.description26 pages
dc.identifierhttps://arxiv.org/abs/math/0610385
dc.identifierhttp://arxiv.org/abs/math/0610385
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/117934
dc.subjectCombinatorics
dc.subjectMetric Geometry
dc.subject52A20; 52A27; 52A21; 52B55; 68W25; 68Q25
dc.titleAn Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods
dc.typetext

Files

Collections

arXiv