Back to Search
Start Over
AN ETH-TIGHT EXACT ALGORITHM FOR EUCLIDEAN TSP.
- Source :
-
SIAM Journal on Computing . 2023, Vol. 52 Issue 3, p740-760. 21p. - Publication Year :
- 2023
-
Abstract
- We study exact algorithms for Metric TSP in Rd. In the early 1990s, algorithms with nO(\surd n) running time were presented for the planar case, and some years later an algorithm with nO(n1 1/d) running time was presented for any d \geqslant 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Metric TSP, except for a lower bound stating that the problem admits no 2o(n1 1/d) algorithm unless ETH fails. In this paper we settle the complexity of Metric TSP, up to constant factors in the exponent and under ETH, by giving an algorithm with running time 2O(n1 1/d). [ABSTRACT FROM AUTHOR]
- Subjects :
- *EUCLIDEAN algorithm
*BOUND states
*ALGORITHMS
Subjects
Details
- Language :
- English
- ISSN :
- 00975397
- Volume :
- 52
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 169737275
- Full Text :
- https://doi.org/10.1137/22M1469122