An ETH-Tight Exact Algorithm for Euclidean TSP

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

doi:10.1137/22M1469122

An ETH-Tight Exact Algorithm for Euclidean TSP

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

Research output: Contribution to journal › Article › Academic › peer-review

2 Citations (Scopus)

192 Downloads (Pure)

Abstract

We study exact algorithms for Metric TSP in ℝ^d. In the early 1990s, algorithms with (Formula Presented) running time were presented for the planar case, and some years later an algorithm with (Formula Presnted) 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 (Formula Presented) 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 Presented).

Original language	English
Pages (from-to)	740-760
Number of pages	21
Journal	SIAM Journal on Computing
Volume	52
Issue number	3
DOIs	https://doi.org/10.1137/22M1469122
Publication status	Published - 2023

Funding

Funding: This work was supported by the NETWORKS project funded by the Netherlands Organization for Scientific Research under grant 024.002.003.

Funders	Funder number
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003

Keywords

Euclidean traveling salesman
separator theroem
subexponential algorithm

Access to Document

10.1137/22M1469122

pdfFinal published version, 618 KB

Cite this

@article{491ee10a62f2491595ce6548f3752b86,

title = "An ETH-Tight Exact Algorithm for Euclidean TSP",

abstract = "We study exact algorithms for Metric TSP in ℝd. In the early 1990s, algorithms with (Formula Presented) running time were presented for the planar case, and some years later an algorithm with (Formula Presnted) 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 (Formula Presented) 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 Presented).",

keywords = "Euclidean traveling salesman, separator theroem, subexponential algorithm",

author = "{de Berg}, Mark and Bodlaender, {Hans L.} and S{\'a}ndor Kisfaludi-Bak and Sudeshna Kolay",

year = "2023",

doi = "10.1137/22M1469122",

language = "English",

volume = "52",

pages = "740--760",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics (SIAM)",

number = "3",

}

TY - JOUR

T1 - An ETH-Tight Exact Algorithm for Euclidean TSP

AU - de Berg, Mark

AU - Bodlaender, Hans L.

AU - Kisfaludi-Bak, Sándor

AU - Kolay, Sudeshna

PY - 2023

Y1 - 2023

N2 - We study exact algorithms for Metric TSP in ℝd. In the early 1990s, algorithms with (Formula Presented) running time were presented for the planar case, and some years later an algorithm with (Formula Presnted) 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 (Formula Presented) 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 Presented).

AB - We study exact algorithms for Metric TSP in ℝd. In the early 1990s, algorithms with (Formula Presented) running time were presented for the planar case, and some years later an algorithm with (Formula Presnted) 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 (Formula Presented) 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 Presented).

KW - Euclidean traveling salesman

KW - separator theroem

KW - subexponential algorithm

UR - http://www.scopus.com/inward/record.url?scp=85165727857&partnerID=8YFLogxK

U2 - 10.1137/22M1469122

DO - 10.1137/22M1469122

M3 - Article

AN - SCOPUS:85165727857

SN - 0097-5397

VL - 52

SP - 740

EP - 760

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

An ETH-Tight Exact Algorithm for Euclidean TSP

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this