TSP with neighborhoods of varying size

详细信息	查看全文 | 推荐本文 |

• 作者：Mark de Berg ; Joachim Gudmundsson ; Matthew J. Katz ; Christos Levcopoulos ; Mark H. Overmars and A. Frank van der Stappen
• 关键词：Computational geometry ; Approximation algorithms ; TSP with neighborhoods
• 刊名：Journal of Algorithms
• 出版年：2005
• 期刊代码：70_01966774
• 类别：mt
• 出版时间：2005
• 卷：57
• 期：1
• 页码：22-36
• 文件大小：365 K

摘要

In TSP with neighborhoods (TSPN) we are given a collection g src="http://www.sciencedirect.com/cache/MiamiImageURL/B6WH3-4FVCBVX-1-2/0?wchp=dGLbVzz-zSkWb" alt="Click to view the MathML source" align="absbottom" border="0" height=12 width=13> of regions in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the neighborhoods are of approximately the same size. In this paper we present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat neighborhoods of arbitrary size. We also show that in the general case, where the neighborhoods can overlap and are not required to be convex or fat, TSPN is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P=NP.