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, Sudeshna Kolay

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

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 - 30 Jun 2023

Bibliographical note

Funding Information:
*Received by the editors January 4, 2022; accepted for publication (in revised form) February 6, 2023; published electronically June 5, 2023. An earlier version of this article appeared in the Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, IEEE Computer Society, 2018, pp. 450--461, and the article shares content with the third author's thesis prepared at Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, 2019. https://doi.org/10.1137/22M1469122 Funding: This work was supported by the NETWORKS project funded by the Netherlands Organization for Scientific Research under grant 024.002.003. \dagger Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5600 MB, The Netherlands ([email protected]). \ddagger Department of Computer Science, Utrecht University, Utrecht 3508 TB, The Netherlands ([email protected]). \S Department of Computer Science, Aalto University, Espoo FI-00076, Finland ([email protected]). \P Indian Institute of Technology Kharagpur, Kharagpur, India ([email protected]).

Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

Funding

*Received by the editors January 4, 2022; accepted for publication (in revised form) February 6, 2023; published electronically June 5, 2023. An earlier version of this article appeared in the Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, IEEE Computer Society, 2018, pp. 450--461, and the article shares content with the third author's thesis prepared at Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, 2019. https://doi.org/10.1137/22M1469122 Funding: This work was supported by the NETWORKS project funded by the Netherlands Organization for Scientific Research under grant 024.002.003. \dagger Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5600 MB, The Netherlands ([email protected]). \ddagger Department of Computer Science, Utrecht University, Utrecht 3508 TB, The Netherlands ([email protected]). \S Department of Computer Science, Aalto University, Espoo FI-00076, Finland ([email protected]). \P Indian Institute of Technology Kharagpur, Kharagpur, India ([email protected]).

Keywords

Euclidean traveling salesman
separator theroem
subexponential algorithm

Access to Document

10.1137/22M1469122

22m1469122Final published version, 618 KBLicence: Taverne

Cite this

@article{ab8f0decc8ef4158a17f9e31f545fc22,

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\textbackslash{}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",

note = "Funding Information: *Received by the editors January 4, 2022; accepted for publication (in revised form) February 6, 2023; published electronically June 5, 2023. An earlier version of this article appeared in the Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, IEEE Computer Society, 2018, pp. 450--461, and the article shares content with the third author's thesis prepared at Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, 2019. https://doi.org/10.1137/22M1469122 Funding: This work was supported by the NETWORKS project funded by the Netherlands Organization for Scientific Research under grant 024.002.003. \textbackslash{}dagger Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5600 MB, The Netherlands ([email protected]). \textbackslash{}ddagger Department of Computer Science, Utrecht University, Utrecht 3508 TB, The Netherlands ([email protected]). \textbackslash{}S Department of Computer Science, Aalto University, Espoo FI-00076, Finland ([email protected]). \textbackslash{}P Indian Institute of Technology Kharagpur, Kharagpur, India ([email protected]). Publisher Copyright: Copyright {\textcopyright} by SIAM. Unauthorized reproduction of this article is prohibited.",

year = "2023",

month = jun,

day = "30",

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 Publications",

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

N1 - Funding Information: *Received by the editors January 4, 2022; accepted for publication (in revised form) February 6, 2023; published electronically June 5, 2023. An earlier version of this article appeared in the Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, IEEE Computer Society, 2018, pp. 450--461, and the article shares content with the third author's thesis prepared at Technische Universiteit Eindhoven, Department of Mathematics and Computer Science, 2019. https://doi.org/10.1137/22M1469122 Funding: This work was supported by the NETWORKS project funded by the Netherlands Organization for Scientific Research under grant 024.002.003. \dagger Department of Mathematics and Computer Science, Eindhoven University of Technology, Eindhoven 5600 MB, The Netherlands ([email protected]). \ddagger Department of Computer Science, Utrecht University, Utrecht 3508 TB, The Netherlands ([email protected]). \S Department of Computer Science, Aalto University, Espoo FI-00076, Finland ([email protected]). \P Indian Institute of Technology Kharagpur, Kharagpur, India ([email protected]). Publisher Copyright: Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PY - 2023/6/30

Y1 - 2023/6/30

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 - https://www.scopus.com/pages/publications/85165727857

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

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this