TSP with neighborhoods of varying size
Publikation/Tidskrift/Serie: Algorithms — ESA 2002 / Lecture notes in computer science
Förlag: Springer Berlin / Heidelberg
In TSP with neighborhoods we are given a set of objects 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 objects are of approximately the same size. We present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat objects of arbitrary size. We also show that the problem is APX-hard and cannot be approximated within a factor of 391/390 in polynomial time, unless P=NP.
- Computer Science
10th Annual European Symposium on Algorithms, ESA 2002
- ISSN: 0302-9743