On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2022-06-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
21
Series
18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022, pp. 1-21, Leibniz International Proceedings in Informatics, LIPIcs ; Volume 227
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 Rd, with d ≥ 3, are NP-hardness and an O(log3 n)-approximation algorithm which is based on a reduction to the group Steiner tree problem. We show that TSP with lines in Rd 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(log2 n)-approximation algorithm for the problem, albeit with a running time of nO(log log n).Description
Funding Information: Related Version The article has an earlier version available on ArXiv. Full Version: https://arxiv.org/abs/2008.12075 Funding Antonios Antoniadis: 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. Daniel Vaz: 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. Publisher Copyright: © 2022 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
Keywords
Geometric approximation algorithms, Group Steiner Tree, Traveling Salesman with neighborhoods
Other note
Citation
Antoniadis, A, Kisfaludi-Bak, S, Laekhanukit, B & Vaz, D 2022, On the Approximability of the Traveling Salesman Problem with Line Neighborhoods . in A Czumaj & Q Xin (eds), 18th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2022 ., 10, Leibniz International Proceedings in Informatics, LIPIcs, vol. 227, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-21, Scandinavian Symposium and Workshops on Algorithm Theory, Torshavn, Faroe Islands, 27/06/2022 . https://doi.org/10.4230/LIPIcs.SWAT.2022.10