Document Open Access Logo

A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics

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

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.15.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Author Details

T-H. Hubert Chan
  • Department of Computer Science, The University of Hong Kong, Hong Kong, China
Haotian Jiang
  • Department of Physics, Tsinghua University, Beijing, China
Shaofeng H.-C. Jiang
  • The Weizmann Institute of Science, Rehovot, Israel

Funding

  • Chan, T-H. Hubert: This work was partially supported by the Hong Kong RGC under the grant 17217716.
  • Jiang, Haotian: This research is supported in part by the National Basic Research Program of China Grant 2015CB358700, the National Natural Science Foundation of China Grant 61772297, 61632016, 61761146003, and a grant from Microsoft Research Asia.

Cite As Get BibTex

T-H. Hubert Chan, Haotian Jiang, and Shaofeng H.-C. Jiang. A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 15:1-15:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.15

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Routing and network design problems
Keywords
  • Doubling Dimension
  • Traveling Salesman Problem
  • Polynomial Time Approximation Scheme
  • Steiner Tree Problem
  • Prize Collecting

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, and Howard J. Karloff. Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput., 40(2):309-332, 2011. Google Scholar
  2. Sanjeev Arora. Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM, 45(5):753-782, 1998. Google Scholar
  3. P. Assouad. Plongements lipschitziens dans R^n. Bull. Soc. Math. France, 111(4):429-448, 1983. Google Scholar
  4. Egon Balas. The prize collecting traveling salesman problem. Networks, 19(6):621-636, 1989. Google Scholar
  5. Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45(4):1563-1581, 2016. Google Scholar
  6. M Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, and Dániel Marx. Prize-collecting steiner problems on planar graphs. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1028-1049. Society for Industrial and Applied Mathematics, 2011. Google Scholar
  7. MohammadHossein Bateni and MohammadTaghi Hajiaghayi. Euclidean prize-collecting steiner forest. Algorithmica, 62(3-4):906-929, 2012. Google Scholar
  8. Daniel Bienstock, Michel X Goemans, David Simchi-Levi, and David Williamson. A note on the prize collecting traveling salesman problem. Mathematical programming, 59(1):413-420, 1993. Google Scholar
  9. Glencora Borradaile, Philip N. Klein, and Claire Mathieu. A polynomial-time approximation scheme for euclidean steiner forest. ACM Trans. Algorithms, 11(3):19:1-19:20, 2015. Google Scholar
  10. T.-H. Hubert Chan, Shuguang Hu, and Shaofeng H.-C. Jiang. A PTAS for the steiner forest problem in doubling metrics. In FOCS, pages 810-819. IEEE Computer Society, 2016. Google Scholar
  11. T.-H. Hubert Chan, Haotian Jiang, and Shaofeng H.-C. Jiang. A unified PTAS for prize collecting TSP and steiner tree problem in doubling metrics. CoRR, abs/1710.07774, 2017. Google Scholar
  12. T.-H. Hubert Chan and Shaofeng H.-C. Jiang. Reducing curse of dimensionality: Improved PTAS for TSP (with neighborhoods) in doubling metrics. In SODA, pages 754-765. SIAM, 2016. Google Scholar
  13. Kenneth L. Clarkson. Nearest neighbor queries in metric spaces. Discrete & Computational Geometry, 22(1):63-93, 1999. URL: http://dx.doi.org/10.1007/PL00009449.
  14. Erik D Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi. Contraction decomposition in h-minor-free graphs and algorithmic applications. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 441-450. ACM, 2011. Google Scholar
  15. M. M. Deza and M. Laurent. Geometry of cuts and metrics, volume 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin, 1997. Google Scholar
  16. Michel X Goemans. Combining approximation algorithms for the prize-collecting tsp. arXiv preprint arXiv:0910.0553, 2009. Google Scholar
  17. Michel X. Goemans and David P. Williamson. A general approximation technique for constrained forest problems. SIAM J. Comput., 24(2):296-317, 1995. Google Scholar
  18. Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In FOCS, pages 534-543. IEEE Computer Society, 2003. Google Scholar
  19. J. Matoušek. Lectures on discrete geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. Google Scholar
  20. Kunal Talwar. Bypassing the embedding: algorithms for low dimensional metrics. In STOC, pages 281-290. ACM, 2004. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact