An ETH-Tight Exact Algorithm for Euclidean TSP

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

doi:10.1109/FOCS.2018.00050

An ETH-Tight Exact Algorithm for Euclidean TSP

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

Eindhoven University of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

We study exact algorithms for Euclidean TSP in R d . In the early 1990s algorithms with n O(√n) running time were presented for the planar case, and some years later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.

Original language	English
Title of host publication	Proceedings 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018
Publisher	IEEE
Pages	450-461
Number of pages	12
ISBN (Electronic)	978-1-5386-4230-6
ISBN (Print)	978-1-5386-4231-3
DOIs	https://doi.org/10.1109/FOCS.2018.00050
Publication status	Published - 2018

Keywords

Particle separators
Approximation algorithms
Computer science
Complexity theory
Hypercubes
Heuristic algorithms

Access to Document

10.1109/FOCS.2018.00050

An_ETH-Tight_Exact_Algorithm_for_Euclidean_TSPFinal published version, 319 KBLicence: Taverne

Cite this

@inproceedings{da655dffa3824201af93511830c57227,

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

abstract = "We study exact algorithms for Euclidean TSP in R d . In the early 1990s algorithms with n O(√n) running time were presented for the planar case, and some years later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.",

keywords = "Particle separators, Approximation algorithms, Computer science, Complexity theory, Hypercubes, Heuristic algorithms",

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

year = "2018",

doi = "10.1109/FOCS.2018.00050",

language = "English",

isbn = "978-1-5386-4231-3",

pages = "450--461",

booktitle = "Proceedings 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018",

publisher = "IEEE",

address = "United States",

}

TY - GEN

T1 - An ETH-Tight Exact Algorithm for Euclidean TSP

AU - Berg, Mark de

AU - Bodlaender, Hans L.

AU - Kisfaludi-Bak, Sándor

AU - Kolay, Sudeshna

PY - 2018

Y1 - 2018

N2 - We study exact algorithms for Euclidean TSP in R d . In the early 1990s algorithms with n O(√n) running time were presented for the planar case, and some years later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.

AB - We study exact algorithms for Euclidean TSP in R d . In the early 1990s algorithms with n O(√n) running time were presented for the planar case, and some years later an algorithm with n O(n1-1/d) running time was presented for any d ≥ 2. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on Euclidean TSP, except for a lower bound stating that the problem admits no 2 O (n 1-1/d-ε ) algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of Euclidean TSP by giving a 2 O(n1-1/d) algorithm and by showing that a 2 o(n1-1/d) algorithm does not exist unless ETH fails.

KW - Particle separators

KW - Approximation algorithms

KW - Computer science

KW - Complexity theory

KW - Hypercubes

KW - Heuristic algorithms

U2 - 10.1109/FOCS.2018.00050

DO - 10.1109/FOCS.2018.00050

M3 - Conference contribution

SN - 978-1-5386-4231-3

SP - 450

EP - 461

BT - Proceedings 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018

PB - IEEE

ER -

An ETH-Tight Exact Algorithm for Euclidean TSP

Abstract

Keywords

Access to Document

Fingerprint

Cite this