2026-08-16T23:38:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20026 2024-06-06T06:21:17Z ddc:004 open_access

Faster Approximation Scheme for Euclidean k-TSP van Wijland, Ernest Zhou, Hang approximation algorithms optimization traveling salesman problem 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⋅2^O(1/ε^{d-1})⋅(log n)^{2d²⋅2^d}. This improves Arora’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(n^d). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ernest van Wijland and Hang Zhou 2024 Is Part Of LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2024.81 urn:nbn:de:0030-drops-200268 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.81 eng https://creativecommons.org/licenses/by/4.0/legalcode