@inproceedings{301c6e6b496e4763b18ac8e0e84c5bef,
title = "Faster Approximation Scheme for Euclidean k-TSP",
abstract = "In the Euclidean k-traveling salesman problem (k-TSP), we are given n points in the d-dimensional Euclidean space, for some fixed constant d ≥ 2, and a positive integer k. The goal is to find a shortest tour visiting at least k points. We give an approximation scheme for the Euclidean k-TSP in time n · 2O(1/εd−1) · (log n)2d2·2d . This improves Arora{\textquoteright}s approximation scheme of running time n·k·(log n)(O(√d/ε))d−1 [J. ACM 1998]. Our algorithm is Gap-ETH tight and can be derandomized by increasing the running time by a factor O(nd).",
keywords = "approximation algorithms, optimization, traveling salesman problem",
author = "\{van Wijland\}, Ernest and Hang Zhou",
note = "Publisher Copyright: {\textcopyright} Ernest van Wijland and Hang Zhou.; 40th International Symposium on Computational Geometry, SoCG 2024 ; Conference date: 11-06-2024 Through 14-06-2024",
year = "2024",
month = jun,
day = "1",
doi = "10.4230/LIPIcs.SoCG.2024.81",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Wolfgang Mulzer and Phillips, \{Jeff M.\}",
booktitle = "40th International Symposium on Computational Geometry, SoCG 2024",
}