A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics
Preprint
Abstract
We present a unified 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 connected 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.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- A PTAS for the Steiner Forest Problem in Doubling Metrics2016
- The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation SchemeSIAM Journal on Computing, 2016
- Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics2015
- New Doubling Spanners: Better and SimplerSIAM Journal on Computing, 2015
- Euclidean Prize-Collecting Steiner ForestAlgorithmica, 2011
- Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSPSIAM Journal on Computing, 2011
- Bounded geometries, fractals, and low-distortion embeddings2004
- Geometry of Cuts and Metrics1997
- A note on the prize collecting traveling salesman problemMathematical Programming, 1993
- The prize collecting traveling salesman problemNetworks, 1989