{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:42:38Z","timestamp":1787341358074,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee","doi-asserted-by":"publisher","award":["17217716"],"award-info":[{"award-number":["17217716"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner forest problem in doubling metrics. Before our work, a PTAS was given only for the Euclidean plane in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115--124]. Our PTAS also shares similarities with the dynamic programming for sparse instances used in [Y. Bartal, L. Gottlieb, and R. Krauthgamer, in STOC, ACM, 2012, pp. 663--672] and [T-H. H. Chan and S.-H. Jiang, in SODA, SIAM, 2016, pp. 754--765]. However, extending previous approaches requires overcoming several nontrivial hurdles, and we make the following technical contributions. (1) We prove a technical lemma showing that Steiner points have to be \u201cnear\u201d the terminals in an optimal Steiner tree. This enables us to define a heuristic to estimate the local behavior of the optimal solution, even though the Steiner points are unknown in advance. This lemma also generalizes previous results in the Euclidean plane and may be of independent interest for related problems involving Steiner points. (2) We develop a novel algorithmic technique known as \u201cadaptive cells\u201d to overcome the difficulty of keeping track of multiple components in a solution. Our idea is based on but significantly different from the previously proposed \u201cuniform cells\u201d in [G. Borradaile, P. N. Klein, and C. Mathieu, in FOCS, IEEE Computer Society, 2008, pp. 115--124], where techniques cannot be readily applied to doubling metrics.<\/jats:p>","DOI":"10.1137\/16m1107206","type":"journal-article","created":{"date-parts":[[2018,8,29]],"date-time":"2018-08-29T12:19:53Z","timestamp":1535545193000},"page":"1705-1734","source":"Crossref","is-referenced-by-count":5,"title":["A PTAS for the Steiner Forest Problem in Doubling Metrics"],"prefix":"10.1137","volume":"47","author":[{"given":"T-H.","family":"Hubert Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shuguang","family":"Hu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shaofeng H.-C.","family":"Jiang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,8,29]]},"reference":[{"key":"atypb1","first-page":"271","author":"Abraham I.","year":"2006","journal-title":"ACM"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"atypb4","first-page":"207","author":"Arora S.","year":"2002","journal-title":"The Netherlands"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"atypb6","first-page":"663","author":"Bartal Y.","year":"2012","journal-title":"ACM"},{"key":"atypb7","first-page":"570","author":"Bateni M.","year":"2016","journal-title":"ACM"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9491-8"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"atypb10","first-page":"115","author":"Borradaile G.","year":"2008","journal-title":"IEEE Computer Society"},{"key":"atypb11","first-page":"583","author":"Byrka J.","year":"2010","journal-title":"ACM"},{"key":"atypb12","first-page":"754","author":"Chan T-H. H.","year":"2016","journal-title":"SIAM"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.046"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1145\/2601070"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"M. M. Deza and M. Laurent,\n                      Geometry of Cuts and Metrics\n                      , Algorithms Combin. 15, Springer-Verlag, Berlin, 1997.","DOI":"10.1007\/978-3-642-04295-9"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1985-0810173-6"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187871"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"atypb20","first-page":"534","author":"Gupta A.","year":"2003","journal-title":"IEEE Computer Society"},{"key":"atypb21","first-page":"871","author":"Gupta A.","year":"2015","journal-title":"ACM"},{"key":"atypb22","first-page":"585","author":"Halperin E.","year":"2003","journal-title":"ACM"},{"key":"atypb23","unstructured":"M. Hauptmann and M. Karpi\u0144ski,\n                      A Compendium on Steiner Tree Problems\n                      , Research Report 85343, Institut f\u00fcr Informatik, University of Bonn, Bonn, Germany, 2013."},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"J. Matou\u0161ek,\n                      Lectures on Discrete Geometry\n                      , Grad. Texts in Math. 212, Springer-Verlag, New York, 2002.","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"atypb25","first-page":"281","author":"Talwar K.","year":"2004","journal-title":"ACM"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1107206","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:14:59Z","timestamp":1787339699000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1107206"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1107206"],"URL":"https:\/\/doi.org\/10.1137\/16m1107206","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}