February 26, 2008 Theory Seminar 4:00 pm, Computer Science 140

"Arora's PTAS for TSP"

Elisha Rosensweig

Abstract: In the classic Traveling Sales Person problem (TSP), a vertex-traversal of a graph is sought that will minimize the accumulated costs of the edges used in the traversal. This problem in NP-hard, and with arbitrary weights also all constant-factor approximations have been shown to be NP-hard.

In this talk, I present a Polynomial Time Approximation Scheme (PTAS), due to S. Arora, for the case of Euclidian TSP. In this scenario, vertices are points in Euclidian space and the weight of an edge is its Euclidian length. Though Euclidian TSP is an NP-hard problem, we shall see that it is possible to find a (1+1/c)-approximation of the optimal route with complexity O(n log(n)^O(c)), for any positive constant c. The talk will focus on the case of vertices in 2-dimensional space, though the results can be expanded to apply to any d-dimensional euclidian space.