DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2023.14

Improved Guarantees for the a Priori TSP

Authors: Jannis Blauth, Meike Neuwohner, Luise Puhlmann, and Jens Vygen

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract

We revisit the a priori TSP (with independent activation) and prove stronger approximation guarantees than were previously known. In the a priori TSP, we are given a metric space (V,c) and an activation probability p(v) for each customer v ∈ V. We ask for a TSP tour T for V that minimizes the expected length after cutting T short by skipping the inactive customers. All known approximation algorithms select a nonempty subset S of the customers and construct a master route solution, consisting of a TSP tour for S and two edges connecting every customer v ∈ V⧵S to a nearest customer in S. We address the following questions. If we randomly sample the subset S, what should be the sampling probabilities? How much worse than the optimum can the best master route solution be? The answers to these questions (we provide almost matching lower and upper bounds) lead to improved approximation guarantees: less than 3.1 with randomized sampling, and less than 5.9 with a deterministic polynomial-time algorithm.

Cite as

Jannis Blauth, Meike Neuwohner, Luise Puhlmann, and Jens Vygen. Improved Guarantees for the a Priori TSP. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{blauth_et_al:LIPIcs.ISAAC.2023.14,
  author =	{Blauth, Jannis and Neuwohner, Meike and Puhlmann, Luise and Vygen, Jens},
  title =	{{Improved Guarantees for the a Priori TSP}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{14:1--14:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.14},
  URN =		{urn:nbn:de:0030-drops-193161},
  doi =		{10.4230/LIPIcs.ISAAC.2023.14},
  annote =	{Keywords: A priori TSP, random sampling, stochastic combinatorial optimization}
}

Search Results

Documents authored by Blauth, Jannis

Improved Guarantees for the a Priori TSP

Abstract

Cite as

Thanks for your feedback!

Could not send message