An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods

Details An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods

2006-10-11

arxiv.org/abs/math/0610385v1

Mathematics

Combinatorics

26 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An Efficient Approximation of the Traveling Salesman Polytope Using Lifting Methods will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-443068