{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T10:41:51Z","timestamp":1775040111408,"version":"3.50.1"},"reference-count":21,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong RGC","award":["17217716"],"award-info":[{"award-number":["17217716"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/3378571","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:33:40Z","timestamp":1583789620000},"page":"1-23","update-policy":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["A Unified PTAS for Prize Collecting TSP and Steiner Tree Problem in Doubling Metrics"],"prefix":"10.1145","volume":"16","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[{"name":"University of Hong Kong, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Haotian","family":"Jiang","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaofeng H.-C.","family":"Jiang","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132557"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771429"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230190602"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/130913328"},{"key":"e_1_2_1_7_1","volume-title":"Nitish Korula, and D\u00e1niel Marx.","author":"Bateni Mohammad Hossein","year":"2011","unstructured":"Mohammad Hossein Bateni , Chandra Chekuri , Alina Ene , Mohammad Taghi Hajiaghayi , Nitish Korula, and D\u00e1niel Marx. 2011 . Prize-collecting Steiner problems on planar graphs. In Proceedings of the SODA. SIAM , 1028--1049. Mohammad Hossein Bateni, Chandra Chekuri, Alina Ene, Mohammad Taghi Hajiaghayi, Nitish Korula, and D\u00e1niel Marx. 2011. Prize-collecting Steiner problems on planar graphs. In Proceedings of the SODA. SIAM, 1028--1049."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9491-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01581256"},{"key":"e_1_2_1_10_1","article-title":"A polynomial-time approximation scheme for Euclidean Steiner forest","volume":"11","author":"Borradaile Glencora","year":"2015","unstructured":"Glencora Borradaile , Philip N. Klein , and Claire Mathieu . 2015 . A polynomial-time approximation scheme for Euclidean Steiner forest . ACM Trans. Algor. 11 , 3 (2015), 19:1--19:20. Glencora Borradaile, Philip N. Klein, and Claire Mathieu. 2015. A polynomial-time approximation scheme for Euclidean Steiner forest. ACM Trans. Algor. 11, 3 (2015), 19:1--19:20.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1107206"},{"key":"e_1_2_1_12_1","article-title":"Reducing curse of dimensionality: Improved PTAS for TSP (with neighborhoods) in doubling metrics","volume":"14","author":"Hubert Chan T.-H.","year":"2018","unstructured":"T.-H. Hubert Chan and Shaofeng H.-C. Jiang . 2018 . Reducing curse of dimensionality: Improved PTAS for TSP (with neighborhoods) in doubling metrics . ACM Trans. Algor. 14 , 1 (2018), 9:1--9:18. T.-H. Hubert Chan and Shaofeng H.-C. Jiang. 2018. Reducing curse of dimensionality: Improved PTAS for TSP (with neighborhoods) in doubling metrics. ACM Trans. Algor. 14, 1 (2018), 9:1--9:18.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/130930984"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993696"},{"key":"e_1_2_1_16_1","volume-title":"Geometry of Cuts and Metrics. Algorithms and Combinatorics","volume":"15","author":"Deza M. M.","unstructured":"M. M. Deza and M. Laurent . 1997 . Geometry of Cuts and Metrics. Algorithms and Combinatorics , Vol. 15 . Springer-Verlag, Berlin. xii+587 pages. M. M. Deza and M. Laurent. 1997. Geometry of Cuts and Metrics. Algorithms and Combinatorics, Vol. 15. Springer-Verlag, Berlin. xii+587 pages."},{"key":"e_1_2_1_17_1","volume-title":"Combining approximation algorithms for the prize-collecting TSP. CoRR abs\/0910.0553","author":"Goemans Michel X.","year":"2009","unstructured":"Michel X. Goemans . 2009. Combining approximation algorithms for the prize-collecting TSP. CoRR abs\/0910.0553 ( 2009 ). Michel X. Goemans. 2009. Combining approximation algorithms for the prize-collecting TSP. CoRR abs\/0910.0553 (2009)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_2_1_19_1","volume-title":"Lee","author":"Gupta Anupam","year":"2003","unstructured":"Anupam Gupta , Robert Krauthgamer , and James R . Lee . 2003 . Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the FOCS. IEEE Computer Society , 534--543. Anupam Gupta, Robert Krauthgamer, and James R. Lee. 2003. Bounded geometries, fractals, and low-distortion embeddings. In Proceedings of the FOCS. IEEE Computer Society, 534--543."},{"key":"e_1_2_1_20_1","volume-title":"Lectures on Discrete Geometry. Graduate Texts in Mathematics","author":"Matou\u0161ek J.","unstructured":"J. Matou\u0161ek . 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics , Vol. 212 . Springer-Verlag , New York . xvi+481 pages. J. Matou\u0161ek. 2002. Lectures on Discrete Geometry. Graduate Texts in Mathematics, Vol. 212. Springer-Verlag, New York. xvi+481 pages."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007399"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3378571","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/pdf\/10.1145\/3378571","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:19Z","timestamp":1750200079000},"score":1,"resource":{"primary":{"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/dl.acm.org\/doi\/10.1145\/3378571"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":21,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3378571"],"URL":"https:\/\/2.zoppoz.workers.dev:443\/https\/doi.org\/10.1145\/3378571","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"2018-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}