EUVIMEDEUVIMED entdecken
Crossref

An ETH-Tight Exact Algorithm for Euclidean TSP

Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Sudeshna Kolay

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →