Abstract
We prove that various geometric covering problems, related to the Travelling Salesman Problem cannot be efficiently approximated to within any constant factor unless P=NP. This includes the Group-Travelling Salesman Problem (TSP with Neighborhoods) in the Euclidean plane, the Group-Steiner-Tree in the Euclidean plane and the Minimum Watchman Tour and the Minimum Watchman Path in 3-D. Some inapproximability factors are also shown for special cases of the above problems, where the size of the sets is bounded. Group-TSP and Group-Steiner-Tree where each neighbourhood is connected are also considered. It is shown that approximating these variants to within any constant factor smaller than 2, is NP-hard.
Research supported in part by the Fund for Basic Research Administered by the Israel Academy of Sciences, and a Bikura grant.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arkin, E., Hassin, R.: Approximation algorithms for the geometric covering salesman problem. DAMATH: Discrete Applied Mathematics and Combinatorial Operations Research and Computer Science 55(3), 197–218 (1994)
Arora, S.: Polynomial-time approximation scheme for Euclidean TSP and other geometric problems. In: Proceedings of the Symposium on Foundations of Computer Science, pp. 2–11 (1996)
Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. Technical report, Graduate School of Industrial Administration, Carnegy–Mellon University (1976)
Carlsson, S., Jonsson, H., Nilsson, B.J.: Finding the shortest watchman route in a simple polygon. GEOMETRY: Discrete X Computational Geometry 22(3), 377–402 (1999)
Chin, W., Ntafos, S.: Optimum watchman routes. Information. Processing Letters 28(1), 39–44 (1988)
Carr, R.D., Vempala, S., Mandler, J.: Towards a 4/3 approximation for the asymmetric traveling salesman problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, January 9–11, pp. 116–125. ACM Press, N.Y (2000)
de Berg, M., Gudmundsson, J., Katz, M.J., Levcopoulos, C., Overmars, M.H., van der Stappen, A.F.: TSP with neighborhoods of varying size. In: ESA: Annual European Symposium on Algorithms, pp. 187–199 (2002)
Dinur, I., Guruswami, V., Khot, S., Regev, O.: A new multilayered pcp and the hardness of hypergraph vertex cover. In: Proceedings of the thirty-fifth ACM symposium on Theory of computing, pp. 595–601. ACM Press, New York (2003)
Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), January 7-9, pp. 38–46. ACM Press, New York (2001)
Engebretsen, L., Karpinski, M.: Approximation hardness of TSP with bounded metrics. In: ICALP: Annual International Colloquium on Automata, Languages and Programming, pp. 201–212 (2001)
Feige, U.: A threshold of ln n for approximating set cover. JACM: Journal of the ACM 45(4), 634–652 (1998)
Frieze, A., Galbiati, G., Maffioli, F.: On the worst-case performance of some algorithms for the asymmetric travelling salesman problem. Networks 12, 23–39 (1982)
Garey, M.R., Graham, R.L., Johnson, D.S.: Some NP-complete geometric problems. In: Conference Record of the Eighth Annual ACM Symposium on Theory of Computing, Hershey, Pennsylvania, May 3–5, pp. 10–22 (1976)
Garey, M.R., Graham, R.L., Johnson, D.S.: The complexity of computing Steiner minimal trees. SIAM Journal on Applied Mathematics 32(4), 835–859 (1977)
Gudmundsson, J., Levcopoulos, C.: A fast approximation algorithm for TSP with neighborhoods. Nordic Journal of Computing 6(4), 469–488 (1999)
Gewali, L., Ntafos, S.C.: Watchman routes in the presence of a pair of convex polygons. Information Sciences 105(1-4), 123–149 (1998)
Ihler, E.: The complexity of approximating the class Steiner tree problem. In: Schmidt, G., Berghammer, R. (eds.) WG 1991. LNCS, vol. 570, pp. 85–96. Springer, Heidelberg (1992)
Lund, C., Yannakakis, M.: On the hardness of approximating minimization problems. JACM 41(5), 960–981 (1994)
Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple new method for the geometric k-MST problem. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, Atlanta, Georgia, January 28–30, pp. 402–408 (1996)
Mitchell, J.S.B.: Geometric Shortest Paths and Network optimization, preliminary edn. Elsevier Science, Amsterdam (2000)
Mata, C., Mitchell, J.S.B.: Approximation algorithms for geometric tour and network design problems. In: Proceedings of the 11th Annual Symposium on Computational Geometry, pp. 360–369. ACM Press, New York (1995)
Nilsson, B.J., Wood, D.: Optimum watchmen in spiral polygons. In: CCCG: Canadian Conference in Computational Geometry, pp. 269–272 (1990)
Papadimitriou, C.H.: Euclidean TSP is NP-complete. Theoretical Computer Science 4, 237–244 (1977)
Petrank, E.: The hardness of approximation: Gap location. Computational Complexity 4(2), 133–157 (1994)
Papadimitriou, C.H., Vempala, S.: On the approximability of the traveling salesman problem. In: ACM (ed.) Proceedings of the thirty second annual ACM Symposium on Theory of Computing, Portland, Oregon, May 21–23, pp. 126–133. ACM Press, New York (2000) (extended abstract)
Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, pp. 475–484. ACM Press, New York (1997)
Slavik, P.: The errand scheduling problem. Technical Report 97-02, SUNY at Buffalo, March 14 (1997)
Xue-Hou, T., Hirata, T., Inagaki, Y.: An incremental algorithm for constructing shortest watchman routes. International Journal of Computational Geometry and Applications 3(4), 351–365 (1993)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Safra, S., Schwartz, O. (2003). On the Complexity of Approximating TSP with Neighborhoods and Related Problems. In: Di Battista, G., Zwick, U. (eds) Algorithms - ESA 2003. ESA 2003. Lecture Notes in Computer Science, vol 2832. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-39658-1_41
Download citation
DOI: https://doi.org/10.1007/978-3-540-39658-1_41
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20064-2
Online ISBN: 978-3-540-39658-1
eBook Packages: Springer Book Archive