An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods

2006/10/11 by Ellen Veomett, Veomett, Ellen
Mathematics · #52A20 #52A21 #52A27 #52B55 #68Q25 #68W25 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG) #math.CO #math.MG #msc:52A20 #msc:52A21 #msc:52A27 #msc:52B55 #msc:68Q25 #msc:68W25

paper · pdf · doi:10.48550/arxiv.math/0610385

26 pages

arxiv created 2006/10/11 · arxiv updated 2009/12/01

Abstract

For 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.

Related

• A Positive Semidefinite Approximation of the Symmetric Traveling Salesman Polytope
• On the facial structure of Symmetric and Graphical Traveling Salesman Polyhedra
• The traveling salesman problem for lines, balls and planes
• A PTAS for Euclidean TSP with Hyperplane Neighborhoods
• A O(n⁸) X O(n⁷) Linear Programming Model of the Traveling Salesman Problem