DROPS

Document

DOI: 10.4230/LIPIcs.SoCG.2024.81

Faster Approximation Scheme for Euclidean k-TSP

Authors: Ernest van Wijland and Hang Zhou

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

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⋅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).

Cite as

Ernest van Wijland and Hang Zhou. Faster Approximation Scheme for Euclidean k-TSP. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 81:1-81:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanwijland_et_al:LIPIcs.SoCG.2024.81,
  author =	{van Wijland, Ernest and Zhou, Hang},
  title =	{{Faster Approximation Scheme for Euclidean k-TSP}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{81:1--81:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.81},
  URN =		{urn:nbn:de:0030-drops-200268},
  doi =		{10.4230/LIPIcs.SoCG.2024.81},
  annote =	{Keywords: approximation algorithms, optimization, traveling salesman problem}
}

Search Results

Documents authored by van Wijland, Ernest

Faster Approximation Scheme for Euclidean k-TSP

Abstract

Cite as

Thanks for your feedback!

Could not send message