An ETH-Tight Exact Algorithm for Euclidean TSP
SIAM Journal on Computing · 30.06.2023 · 52 (3) · 740-760
DOI: 10.1137/22m1469122 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 05.06.2023. Verfasst von Mark de Berg und 3 weiteren Autor:innen. Die Arbeit wurde bisher 5-mal zitiert (Crossref) und nennt 29 Literaturangaben. Gefördert von: Netherlans Organization for Scientific Research.
Abstract (Originalsprache)
We study exact algorithms for Metric TSP in [Formula: see text]. In the early 1990s, algorithms with [Formula: see text] running time were presented for the planar case, and some years later an algorithm with [Formula: see text] running time was presented for any [Formula: see text]. 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 [Formula: see text] 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 [Formula: see text].
Förderung
- Netherlans Organization for Scientific Research
Zitieren
APA
Berg, M. D., Bodlaender, H. L., Kisfaludi-Bak, S., & Kolay, S. (2023). An ETH-Tight Exact Algorithm for Euclidean TSP. SIAM Journal on Computing, 52(3), 740-760. https://doi.org/10.1137/22m1469122
Vancouver
Berg MD, Bodlaender HL, Kisfaludi-Bak S, Kolay S. An ETH-Tight Exact Algorithm for Euclidean TSP. SIAM Journal on Computing. 2023;52(3):740-760. doi:10.1137/22m1469122
BibTeX
@article{Berg2023,
author = {Berg, Mark de and Bodlaender, Hans L. and Kisfaludi-Bak, Sándor and Kolay, Sudeshna},
title = {An ETH-Tight Exact Algorithm for Euclidean TSP},
journal = {SIAM Journal on Computing},
year = {2023},
volume = {52},
number = {3},
pages = {740--760},
doi = {10.1137/22m1469122}
}
EUVIMED