Euclidean TSP in Narrow Strips
Loading...
Access rights
openAccess
acceptedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
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)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
51
Series
Discrete & Computational Geometry, Volume 71, issue 4, pp. 1456-1506
Abstract
We investigate how the complexity of Euclidean TSP for point sets P inside the strip (- ∞, + ∞) × [0 , δ] depends on the strip width δ . We obtain two main results. For the case where the points have distinct integer x-coordinates, we prove that a shortest bitonic tour (which can be computed in O(nlog 2n) time using an existing algorithm) is guaranteed to be a shortest tour overall when δ⩽22 , a bound which is best possible.We present an algorithm that is fixed-parameter tractable with respect to δ . Our algorithm has running time 2O(δ)n+O(δ2n2) for sparse point sets, where each 1 × δ rectangle inside the strip contains O(1) points. For random point sets, where the points are chosen uniformly at random from the rectangle [0 , n] × [0 , δ] , it has an expected running time of 2O(δ)n . These results generalise to point sets P inside a hypercylinder of width δ . In this case, the factors 2O(δ) become 2O(δ1-1/d) .Description
Funding Information: This study was supported by Dutch Research council (NWO) under project no. NETWORKS-024.002.003. Funding Information: The work in this paper is supported by the Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003. Publisher Copyright: © 2024, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
Other note
Citation
Alkema, H, de Berg, M, van der Hofstad, R & Kisfaludi-Bak, S 2024, 'Euclidean TSP in Narrow Strips', Discrete & Computational Geometry, vol. 71, no. 4, pp. 1456-1506. https://doi.org/10.1007/s00454-023-00609-7