A PTAS for TSP with neighborhoods among fat regions in the plane

ABSTRACT

The Euclidean TSP with neighborhoods (TSPN) problem seeks a shortest tour that visits a given collection of n regions (neighborhoods). We present the first polynomial-time approximation scheme for TSPN for a set of regions given by arbitrary disjoint fat regions in the plane. This improves substantially upon the known approximation algorithms, and is the first PTAS for TSPN on regions of non-comparable sizes. Our result is based on a novel extension of the m-guillotine method. The result applies to regions that are "fat" in a very weak sense: each region Pi contains a disk of radius Ω(diam(Pi)), but is otherwise arbitrary. Further, the result applies even if the regions intersect arbitrarily, provided that there exists a packing of disjoint disks, of radii Ω(diam(Pi)), contained within their respective regions. Finally, the PTAS result applies also to the case in which the regions are sets of points or polygons, each each lying within one of a given set of disjoint fat regions.

REFERENCES

• 1: Esther M. Arkin , Refael Hassin, Approximation algorithms for the geometric covering salesman problem, Discrete Applied Mathematics, v.55 n.3, p.197-218, Dec. 13, 1994 [doi>10.1016/0166-218X(94)90008-6]
• 2: Sanjeev Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, Journal of the ACM (JACM), v.45 n.5, p.753-782, Sept. 1998 [doi>10.1145/290179.290180]
• 3: S. Arora. Approximation schemes for NP-hard geometric optimization problems: A survey. Mathematical Programming, 97(1--2):43--69, 2003.
• 4: Mark de Berg , Joachim Gudmundsson , Matthew J. Katz , Christos Levcopoulos , Mark H. Overmars , A. Frank van der Stappen, TSP with neighborhoods of varying size, Journal of Algorithms, v.57 n.1, p.22-36, September 2005 [doi>10.1016/j.jalgor.2005.01.010]
• 5: M. Dror and J. B. Orlin. Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. Technical report, MIT, 2004.
• 6: Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Journal of Algorithms, v.48 n.1, p.135-159, August 2003 [doi>10.1016/S0196-6774(03)00047-6]
• 7: K. Elbassioni, A. V. Fishkin, N. H. Mustafa, and R. Sitters. Approximation algorithms for Euclidean group TSP. In Proc. 32nd Internat. Colloq. Automata Lang. Prog., volume 3580 of Lecture Notes Comput. Sci., pages 1115--1126. Springer-Verlag, 2005.
• 8: K. Elbassioni, A. V. Fishkin, and R. Sitters. On approximating the TSP with intersecting neighborhoods. In Proc. 17th Annu. Internat. Sympos. Algorithms Comput., to appear, Dec. 2006.
• 9: C. Feremans and A. Grigoriev. Approximation schemes for the generalized geometric problems with geographic clustering. In Abstracts 21st European Workshop Comput. Geom., page xxx, 2005.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: Joachim Gudmundsson , Christos Levcopoulos, A fast approximation algorithm for TSP with neighborhoods, Nordic Journal of Computing, v.6 n.4, p.469-488, Winter 1999
• 12: Cristian S. Mata , Joseph S. B. Mitchell, Approximation algorithms for geometric tour and network design problems (extended abstract), Proceedings of the eleventh annual symposium on Computational geometry, p.360-369, June 05-07, 1995, Vancouver, British Columbia, Canada [doi>10.1145/220279.220318]
• 13: J. S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: Part III--Faster polynomial-time approximation schemes for geometric network optimization. Manuscript, University at Stony Brook, 1997.
• 14: Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems, SIAM Journal on Computing, v.28 n.4, p.1298-1309, Aug. 1999 [doi>10.1137/S0097539796309764]
• 15: J. S. B. Mitchell. Geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633--701. Elsevier Science Publishers B. V. North-Holland, Amsterdam, 2000.
• 16: Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 17: C. H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theoret. Comput. Sci., 4:237--244, 1977.
• 18: Satish B. Rao , Warren D. Smith, Approximating geometrical graphs via “spanners” and “banyans”, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.540-550, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276868]
• 19: S. Safra and O. Schwartz. On the complexity of approximating tsp with neighborhoods and related problems. In Proc. 11th Annu. European Sympos. Algorithms, volume 2832 of Lecture Notes Comput. Sci., pages 446--458. Springer-Verlag, 2003.