Document Open Access Logo

On the Approximability of the Traveling Salesman Problem with Line Neighborhoods

Authors Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, Daniel Vaz

PDF
Thumbnail PDF

File

LIPIcs.SWAT.2022.10.pdf
  • Filesize: 0.88 MB
  • 21 pages

Document Identifiers

Author Details

Antonios Antoniadis
  • University of Twente, Enschede, The Netherlands
Sándor Kisfaludi-Bak
  • Aalto University, Finland
Bundit Laekhanukit
  • Shanghai University of Finance and Economics, China
Daniel Vaz
  • Operations Research Group, Technische Universität München, Germany

Funding

  • Antoniadis, Antonios: Work done in part while the author was at Saarland University and Max Planck Institute for Informatics and supported by DFG grant AN 1262/1-1.
  • Vaz, Daniel: This work has been supported by the Alexander von Humboldt Foundation with funds from the German Federal Ministry of Education and Research (BMBF). Work done in part while the author was at Saarland University and Max Planck Institute for Informatics.

Cite As Get BibTex

Antonios Antoniadis, Sándor Kisfaludi-Bak, Bundit Laekhanukit, and Daniel Vaz. On the Approximability of the Traveling Salesman Problem with Line Neighborhoods. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SWAT.2022.10

Abstract

We study the variant of the Euclidean Traveling Salesman problem where instead of a set of points, we are given a set of lines as input, and the goal is to find the shortest tour that visits each line. The best known upper and lower bounds for the problem in ℝ^d, with d ≥ 3, are NP-hardness and an O(log³ n)-approximation algorithm which is based on a reduction to the group Steiner tree problem. 
We show that TSP with lines in ℝ^d is APX-hard for any d ≥ 3. More generally, this implies that TSP with k-dimensional flats does not admit a PTAS for any 1 ≤ k ≤ d-2 unless P = NP, which gives a complete classification regarding the existence of polynomial time approximation schemes for these problems, as there are known PTASes for k = 0 (i.e., points) and k = d-1 (hyperplanes). We are able to give a stronger inapproximability factor for d = O(log n) by showing that TSP with lines does not admit a (2-ε)-approximation in d dimensions under the Unique Games Conjecture. On the positive side, we leverage recent results on restricted variants of the group Steiner tree problem in order to give an O(log² n)-approximation algorithm for the problem, albeit with a running time of n^{O(log log n)}.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Approximation algorithms analysis
Keywords
  • Traveling Salesman with neighborhoods
  • Group Steiner Tree
  • Geometric approximation algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Antonios Antoniadis, Krzysztof Fleszar, Ruben Hoeksma, and Kevin Schewior. A PTAS for Euclidean TSP with hyperplane neighborhoods. In SODA'19, pages 1089-1105. SIAM, 2019. URL: https://doi.org/10.1137/1.9781611975482.67.
  2. Esther M. Arkin and Refael Hassin. Approximation algorithms for the geometric covering salesman problem. Discret. Appl. Math., 55(3):197-218, 1994. Google Scholar
  3. Sanjeev Arora. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753-782, 1998. URL: https://doi.org/10.1145/290179.290180.
  4. Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej Woloszyn. A polynomial-time approximation scheme for weighted planar graph TSP. In SODA'98, pages 33-41. ACM/SIAM, 1998. URL: http://dl.acm.org/citation.cfm?id=314613.314632.
  5. Yair Bartal and Lee-Ad Gottlieb. A linear time approximation scheme for Euclidean TSP. In FOCS'13, pages 698-706. IEEE Computer Society, 2013. URL: https://doi.org/10.1109/FOCS.2013.80.
  6. Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563-1581, 2016. URL: https://doi.org/10.1137/130913328.
  7. Hans L. Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, René Sitters, and Thomas Wolle. On the minimum corridor connection problem and other generalized geometric problems. Comput. Geom., 42(9):939-951, 2009. URL: https://doi.org/10.1016/j.comgeo.2009.05.001.
  8. Jean Bourgain. On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics, 52(1-2):46-52, 1985. Google Scholar
  9. Parinya Chalermsook, Syamantak Das, Guy Even, Bundit Laekhanukit, and Daniel Vaz. Survivable network design for group connectivity in low-treewidth graphs. In APPROX-RANDOM, volume 116 of LIPIcs, pages 8:1-8:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  10. Parinya Chalermsook, Syamantak Das, Bundit Laekhanukit, and Daniel Vaz. Beyond metric embedding: Approximating group Steiner trees on bounded treewidth graphs. In SODA'17, pages 737-751. SIAM, 2017. URL: https://doi.org/10.1137/1.9781611974782.47.
  11. T.-H. Hubert Chan and Shaofeng H.-C. Jiang. Reducing curse of dimensionality: Improved PTAS for TSP (with neighborhoods) in doubling metrics. ACM Trans. Algorithms, 14(1):9:1-9:18, 2018. URL: https://doi.org/10.1145/3158232.
  12. Moses Charikar, Chandra Chekuri, Ashish Goel, and Sudipto Guha. Rounding via trees: Deterministic approximation algorithms for group Steiner trees and k-median. In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 114-123. ACM, 1998. URL: https://doi.org/10.1145/276698.276719.
  13. Chandra Chekuri and Martin Pál. A recursive greedy algorithm for walks in directed graphs. In FOCS'05, pages 245-253. IEEE Computer Society, 2005. URL: https://doi.org/10.1109/SFCS.2005.9.
  14. Andrea E. F. Clementi, Pierluigi Crescenzi, and Gianluca Rossi. On the complexity of approximating colored-graph problems. In COCOON'99, volume 1627 of Lecture Notes in Computer Science, pages 281-290. Springer, 1999. URL: https://doi.org/10.1007/3-540-48686-0_28.
  15. Mark de Berg, Joachim Gudmundsson, Matthew J. Katz, Christos Levcopoulos, Mark H. Overmars, and A. Frank van der Stappen. TSP with neighborhoods of varying size. J. Algorithms, 57(1):22-36, 2005. URL: https://doi.org/10.1016/j.jalgor.2005.01.010.
  16. Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Contraction decomposition in h-minor-free graphs and algorithmic applications. In STOC'11, pages 441-450, 2011. URL: https://doi.org/10.1145/1993636.1993696.
  17. Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell. Touring a sequence of polygons. In STOC'03, pages 473-482. ACM, 2003. URL: https://doi.org/10.1145/780542.780612.
  18. Moshe Dror and James B. Orlin. Combinatorial optimization with explicit delineation of the ground set by a collection of subsets. SIAM J. Discret. Math., 21(4):1019-1034, 2008. URL: https://doi.org/10.1137/050636589.
  19. Adrian Dumitrescu. The traveling salesman problem for lines and rays in the plane. Discrete Math., Alg. and Appl., 4(4):44:1-44:12, 2012. Google Scholar
  20. Adrian Dumitrescu and Joseph S. B. Mitchell. Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms, 48(1):135-159, 2003. URL: https://doi.org/10.1016/S0196-6774(03)00047-6.
  21. Adrian Dumitrescu and Csaba D. Tóth. The traveling salesman problem for lines, balls, and planes. ACM Trans. Algorithms, 12(3):43:1-43:29, 2016. URL: https://doi.org/10.1145/2850418.
  22. Khaled M. Elbassioni, Aleksei V. Fishkin, and René Sitters. Approximation algorithms for the Euclidean traveling salesman problem with discrete and continuous neighborhoods. Int. J. Comput. Geometry Appl., 19(2):173-193, 2009. URL: https://doi.org/10.1142/S0218195909002897.
  23. Lars Engebretsen, Piotr Indyk, and Ryan O'Donnell. Derandomized dimensionality reduction with applications. In SODA'02, pages 705-712. SIAM, 2002. URL: http://dl.acm.org/citation.cfm?id=545381.545476.
  24. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. Approximating metrics by tree metrics. SIGACT News, 35(2):60-70, 2004. URL: https://doi.org/10.1145/992287.992300.
  25. Naveen Garg, Goran Konjevod, and R. Ravi. A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms, 37(1):66-84, 2000. URL: https://doi.org/10.1006/jagm.2000.1096.
  26. Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li. O(log^2 k / log log k)-approximation algorithm for directed Steiner tree: a tight quasi-polynomial-time algorithm. In STOC'19, pages 253-264. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316349.
  27. Eran Halperin and Robert Krauthgamer. Polylogarithmic inapproximability. In STOC'03, pages 585-594. ACM, 2003. URL: https://doi.org/10.1145/780542.780628.
  28. Su Jia and Joseph S. B. Mitchell. Geometric tours to visit and view polygons subject to time lower bounds, 2019. URL: https://www.andrew.cmu.edu/user/sjia1/wrp_with_tlb.pdf.
  29. Håkan Jonsson. The traveling salesman problem for lines in the plane. Inf. Process. Lett., 82(3):137-142, 2002. URL: https://doi.org/10.1016/S0020-0190(01)00259-9.
  30. Subhash Khot. On the power of unique 2-prover 1-round games. In STOC'02, pages 767-775. ACM, 2002. URL: https://doi.org/10.1145/509907.510017.
  31. Subhash Khot, Dor Minzer, and Muli Safra. Pseudorandom sets in Grassmann graph have near-perfect expansion. In FOCS'18, pages 592-601. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00062.
  32. Subhash Khot and Oded Regev. Vertex cover might be hard to approximate to within 2-epsilon. J. Comput. Syst. Sci., 74(3):335-349, 2008. URL: https://doi.org/10.1016/j.jcss.2007.06.019.
  33. Robert Krauthgamer and James R. Lee. Algorithms on negatively curved spaces. In FOCS'06, pages 119-132. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/FOCS.2006.9.
  34. Nathan Linial, Avner Magen, and Michael E Saks. Low distortion Euclidean embeddings of trees. Israel Journal of Mathematics, 106(1):339-348, 1998. Google Scholar
  35. Cristian S. Mata and Joseph S. B. Mitchell. A new algorithm for computing shortest paths in weighted planar subdivisions (extended abstract). In SoCG'97, pages 264-273. ACM, 1997. URL: https://doi.org/10.1145/262839.262983.
  36. Jiří Matoušek. On embedding trees into uniformly convex Banach spaces. Israel Journal of Mathematics, 114(1):221-237, 1999. Google Scholar
  37. Jiri Matoušsek. Lectures on discrete geometry, volume 212. Springer Science & Business Media, 2013. Google Scholar
  38. Joseph S. B. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput., 28(4):1298-1309, 1999. URL: https://doi.org/10.1137/S0097539796309764.
  39. Joseph S. B. Mitchell. A PTAS for TSP with neighborhoods among fat regions in the plane. In SODA'07, pages 11-18. SIAM, 2007. URL: http://dl.acm.org/citation.cfm?id=1283383.1283385.
  40. Joseph S. B. Mitchell. A constant-factor approximation algorithm for TSP with pairwise-disjoint connected neighborhoods in the plane. In SoCG'10, pages 183-191. ACM, 2010. URL: https://doi.org/10.1145/1810959.1810992.
  41. Christos H. Papadimitriou. The Euclidean traveling salesman problem is NP-complete. Theor. Comput. Sci., 4(3):237-244, 1977. Google Scholar
  42. Satish Rao and Warren D. Smith. Approximating geometrical graphs via "spanners" and "banyans". In STOC'98, pages 540-550, 1998. URL: https://doi.org/10.1145/276698.276868.
  43. Shmuel Safra and Oded Schwartz. On the complexity of approximating TSP with neighborhoods and related problems. Comput. Complex., 14(4):281-307, 2006. URL: https://doi.org/10.1007/s00037-005-0200-3.
  44. Luca Trevisan. When Hamming meets Euclid: The approximability of geometric TSP and Steiner tree. SIAM J. Comput., 30(2):475-485, 2000. URL: https://doi.org/10.1137/S0097539799352735.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact