The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

Details The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme

2011-12-03

arxiv.org/abs/1112.0699v1

Computer Science

Computational Complexity

Scientific paper

The Traveling Salesman Problem (TSP) is among the most famous NP-hard optimization problems. We design for this problem a randomized polynomial-time algorithm that computes a (1+eps)-approximation to the optimal tour, for any fixed eps>0, in TSP instances that form an arbitrary metric space with bounded intrinsic dimension. The celebrated results of Arora (A-98) and Mitchell (M-99) prove that the above result holds in the special case of TSP in a fixed-dimensional Euclidean space. Thus, our algorithm demonstrates that the algorithmic tractability of metric TSP depends on the dimensionality of the space and not on its specific geometry. This result resolves a problem that has been open since the quasi-polynomial time algorithm of Talwar (T-04).

Affiliated with

Also associated with

No associations

Rating

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme 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 The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-387513