Abstract | ||
---|---|---|
We revisit the classic task of finding the shortest tour of $n$, points in d-dimensional Euclidean space, for any fixed constant $d\geqslant 2$. We determine the optimal dependence on $\varepsilon$ in the running time of an algorithm that computes a $(1+\varepsilon){-}$ approximate tour, under a plausible assumption, Specifically, we give an algorithm th... |
Year | DOI | Venue |
---|---|---|
2021 | 10.1109/FOCS52979.2021.00043 | 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS) |
Keywords | DocType | ISSN |
Steiner trees,Computer science,Traveling salesman problems,Approximation algorithms,Task analysis | Conference | 0272-5428 |
ISBN | Citations | PageRank |
978-1-6654-2055-6 | 0 | 0.34 |
References | Authors | |
0 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Sándor Kisfaludi-Bak | 1 | 5 | 9.21 |
Jesper Nederlof | 2 | 294 | 24.22 |
Karol Wegrzycki | 3 | 13 | 4.79 |