DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2017.62

Prize-Collecting TSP with a Budget Constraint

Authors: Alice Paul, Daniel Freund, Aaron Ferber, David B. Shmoys, and David P. Williamson

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract

We consider constrained versions of the prize-collecting traveling salesman and the minimum spanning tree problems. The goal is to maximize the number of vertices in the returned tour/tree subject to a bound on the tour/tree cost. We present a 2-approximation algorithm for these problems based on a primal-dual approach. The algorithm relies on finding a threshold value for the dual variable corresponding to the budget constraint in the primal and then carefully constructing a tour/tree that is just within budget. Thereby, we improve the best-known guarantees from 3+epsilon and 2+epsilon for the tree and the tour version, respectively. Our analysis extends to the setting with weighted vertices, in which we want to maximize the total weight of vertices in the tour/tree subject to the same budget constraint.

Cite as

Alice Paul, Daniel Freund, Aaron Ferber, David B. Shmoys, and David P. Williamson. Prize-Collecting TSP with a Budget Constraint. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{paul_et_al:LIPIcs.ESA.2017.62,
  author =	{Paul, Alice and Freund, Daniel and Ferber, Aaron and Shmoys, David B. and Williamson, David P.},
  title =	{{Prize-Collecting TSP with a Budget Constraint}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{62:1--62:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.62},
  URN =		{urn:nbn:de:0030-drops-78375},
  doi =		{10.4230/LIPIcs.ESA.2017.62},
  annote =	{Keywords: approximation algorithms, traveling salesman problem}
}

Search Results

Documents authored by Paul, Alice

Prize-Collecting TSP with a Budget Constraint

Abstract

Cite as

Thanks for your feedback!

Could not send message