A Polynomial Time Approximation Scheme for the Traveling Salesman Problem in Curved Surfaces

The polynomial time approximation scheme (PTAS) for Euclidean traveling salesman problem (TSP) combines the two methods of recursive partition and dynamic programming. Similar techniques have been used to construct PTASes for some other Euclidean combinatorial optimization problems. To extend the applications of this method further, TSP in curved surfaces is studied. Observing that the sphere surface has no recursive regular partition as the plane, for a spherical TSP instance that can be covered by an open hemisphere, which we call a small scale instance, we project it onto a sphere-inscribed square to get a plane TSP instance. We perturb the new instance and construct its partition grid. Then we project the perturbed instance and the grid back onto the sphere surface. Things left, such as dynamic programming and randomization, are the same as the PTAS for the plane TSP. This result is generalized to non-small scale spherical TSP and TSP in a set of other curved surfaces. Because of the irregularity of the projections between the sphere surface and the plane, this method is not a PTAS reduction from the spherical TSP to the plane TSP.