A Polynomial Time Approximation Scheme for the Traveling Salesman Problem in the Sphere Surface

摘要：

We give a polynomial time approximation scheme (PTAS) for the Traveling Salesman Problem (TSP) in the sphere surface. After converting a spherical TSP instance into an Euclidean instance by projection, we run the Euclidean PTAS on this instance to get its dissection quadtree. Then we project the instance, and also its quadtree, back onto the sphere surface, and at last perform dynamic programming to the new spherical instance to find an approximation tour which is also a good approximation solution to the original spherical instance. Finding a boundary square for a spherical TSP instance is no more a trivial sfep as in the plane case.

关键词： TSP approximation algorithm PTAS dynamic programming

作者: Gang Wang Zhigang Luo

作者单位: Computer School National University of Defense Technology Changsha, China

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer Engineering and Applications(2011第三届计算机工程与应用国际会议 ICCEA2011)

会议地点: 海口

会议语种:英文

页码: 484-488

在线出版日期: 2011-07-15（万方平台首次上网日期，不代表论文的发表时间）