A unified PTAS for prize collecting TSP and steiner tree problem in doubling metrics

T. H. Hubert Chan, Haotian Jiang, Shaofeng H.C. Jiang

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

Abstract

We present a unified (randomized) polynomial-time approximation scheme (PTAS) for the prize collecting traveling salesman problem (PCTSP) and the prize collecting Steiner tree problem (PCSTP) in doubling metrics. Given a metric space and a penalty function on a subset of points known as terminals, a solution is a subgraph on points in the metric space, whose cost is the weight of its edges plus the penalty due to terminals not covered by the subgraph. Under our unified framework, the solution subgraph needs to be Eulerian for PCTSP, while it needs to be a tree for PCSTP. Before our work, even a QPTAS for the problems in doubling metrics is not known. Our unified PTAS is based on the previous dynamic programming frameworks proposed in [Talwar STOC 2004] and [Bartal, Gottlieb, Krauthgamer STOC 2012]. However, since it is unknown which part of the optimal cost is due to edge lengths and which part is due to penalties of uncovered terminals, we need to develop new techniques to apply previous divide-and-conquer strategies and sparse instance decompositions.

Original languageEnglish
Title of host publication26th European Symposium on Algorithms, ESA 2018
EditorsHannah Bast, Grzegorz Herman, Yossi Azar
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Print)9783959770811
DOIs
Publication statusPublished - 1 Aug 2018
MoE publication typeA4 Article in a conference publication
EventEuropean Symposia on Algorithms - Helsinki, Finland
Duration: 20 Aug 201822 Aug 2018
Conference number: 26

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume112
ISSN (Print)1868-8969

Conference

ConferenceEuropean Symposia on Algorithms
Abbreviated titleESA
CountryFinland
CityHelsinki
Period20/08/201822/08/2018

Keywords

  • Doubling dimension
  • Polynomial time approximation scheme
  • Prize collecting
  • Steiner tree problem
  • Traveling salesman problem

Fingerprint Dive into the research topics of 'A unified PTAS for prize collecting TSP and steiner tree problem in doubling metrics'. Together they form a unique fingerprint.

Cite this