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

Not published at Aalto University

Research output: Chapter in Book/Report/Conference proceeding › Conference article in proceedings › Scientific › peer-review

Abstract

Original language	English
Title of host publication	2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
Publisher	IEEE
Pages	450-461
Number of pages	12
ISBN (Print)	978-1-5386-4231-3
DOIs	https://doi.org/10.1109/FOCS.2018.00050
Publication status	Published - Oct 2018
MoE publication type	A4 Conference publication
Event	Annual Symposium on Foundations of Computer Science - Paris, France Duration: 7 Oct 2018 → 9 Oct 2018 Conference number: 59

Conference

Conference	Annual Symposium on Foundations of Computer Science
Abbreviated title	FOCS
Country/Territory	France
City	Paris
Period	07/10/2018 → 09/10/2018

Keywords

Particle separators
Approximation algorithms
Computer science
Complexity theory
Hypercubes
Heuristic algorithms

Access to Document

10.1109/FOCS.2018.00050

https://arxiv.org/abs/1807.06933

Cite this

@inproceedings{1d4ac068ec404740b4d413d74a766f3d,

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

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

month = oct,

doi = "10.1109/FOCS.2018.00050",

language = "English",

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

pages = "450--461",

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

publisher = "IEEE",

address = "United States",

note = "Annual Symposium on Foundations of Computer Science, FOCS ; Conference date: 07-10-2018 Through 09-10-2018",

}

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

N1 - Conference code: 59

PY - 2018/10

Y1 - 2018/10

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 article in proceedings

SN - 978-1-5386-4231-3

SP - 450

EP - 461

BT - 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)

PB - IEEE

T2 - Annual Symposium on Foundations of Computer Science

Y2 - 7 October 2018 through 9 October 2018

ER -