{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:45:12Z","timestamp":1781077512902,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":33,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1817\/17"],"award-info":[{"award-number":["1817\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451063","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"1028-1041","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Near-linear time approximation schemes for Steiner tree and forest in low-dimensional spaces"],"prefix":"10.1145","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[{"name":"Hebrew University of Jerusalem, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lee-Ad","family":"Gottlieb","sequence":"additional","affiliation":[{"name":"Ariel University, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"165","volume-title":"Conference on Computational Geometry (CCCG","author":"Aghamolaei Sepideh","year":"2018","unstructured":"Sepideh Aghamolaei and Mohammad Ghodsi. 2018. A Composable Coreset for k-Center in Doubling Metrics. In Conference on Computational Geometry (CCCG 2018). Pages 165."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_3_2_1_3_1","volume-title":"Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45","author":"Arora Sanjeev","year":"1998","unstructured":"Sanjeev Arora. 1998. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 45, 1998. Pages 753\u2013782."},{"key":"e_1_3_2_1_4_1","volume-title":"Plongements lipschitziens dans \\bf R\\sp n. Bull. Soc. Math. France, 111, 4","author":"Assouad P.","year":"1983","unstructured":"P. Assouad. 1983. Plongements lipschitziens dans \\bf R\\sp n. Bull. Soc. Math. France, 111, 4, 1983. Pages 429\u2013448."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.80"},{"key":"e_1_3_2_1_6_1","series-title":"SIAM J. Comput., 45, 4","volume-title":"The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme","author":"Bartal Yair","year":"2016","unstructured":"Yair Bartal, Lee-Ad Gottlieb, and Robert Krauthgamer. 2016. The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput., 45, 4, 2016. Pages 1563\u20131581."},{"key":"e_1_3_2_1_7_1","volume-title":"Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM, 58, 5","author":"Bateni Mohammadhossein","year":"2011","unstructured":"Mohammadhossein Bateni, Mohammadtaghi Hajiaghayi, and D\u00e1niel Marx. 2011. Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM, 58, 5, 2011. Pages 21:1\u201321:37."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Babak Behsaz Zachary Friggstad Mohammad R. Salavatipour and Rohit Sivakumar. 2015. Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median. In ICALP. Pages 116\u2013128.","DOI":"10.1007\/978-3-662-47672-7_10"},{"key":"e_1_3_2_1_9_1","volume-title":"A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. ACM Trans. Algorithms, 11, 3","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. Algorithms, 11, 3, 2015."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.145"},{"key":"e_1_3_2_1_11_1","first-page":"592","volume-title":"Proceedings of the Forty-second ACM Symposium on Theory of Computing. STOC '10","author":"Byrka Jaroslaw","unstructured":"Jaroslaw Byrka, Fabrizio Grandoni, Thomas Rothvo\u00df, and Laura Sanit\\`a. 2010. An Improved LP-based Approximation for Steiner Tree. In Proceedings of the Forty-second ACM Symposium on Theory of Computing. STOC '10. Pages 583\u2013592."},{"key":"e_1_3_2_1_12_1","first-page":"1","article-title":"-C. Jiang. 2018. Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods)","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. 14, 1, 2018.","journal-title":"Doubling Metrics."},{"key":"e_1_3_2_1_13_1","volume-title":"Oct., 2008.","author":"Chleb\u00edk Miroslav","year":"2008","unstructured":"Miroslav Chleb\u00edk and Janka Chleb\u00edkov\u00e1. 2008. The Steiner Tree Problem on Graphs: Inapproximability Results. Theor. Comput. Sci., 406, 3, Oct., 2008."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.138"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"crossref","unstructured":"V. Cohen-Addad A. E. Feldmann and D. Saulpic. 2019. Near-Linear Time Approximations Schemes for Clustering in Doubling Metrics. In FOCS. Pages 540\u2013559.","DOI":"10.1109\/FOCS.2019.00041"},{"key":"e_1_3_2_1_16_1","volume-title":"38th annual ACM symposium on Theory of computing. Pages 574\u2013583.","author":"Cole Richard","unstructured":"Richard Cole and Lee-Ad Gottlieb. 2006. Searching dynamic point sets in spaces with bounded doubling dimension. In 38th annual ACM symposium on Theory of computing. Pages 574\u2013583."},{"key":"e_1_3_2_1_17_1","first-page":"25","volume-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '01","author":"Cole Richard","year":"2001","unstructured":"Richard Cole, Ramesh Hariharan, Moshe Lewenstein, and Ely Porat. 2001. A Faster Implementation of the Goemans-Williamson Clustering Algorithm. In Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms. SODA '01. Pages 17\u201325."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.160998"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.53"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933114"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1127181"},{"key":"e_1_3_2_1_22_1","volume-title":"Deformable spanners and applications. Comput. Geom. Theory Appl., 35, 1","author":"Gao Jie","year":"2006","unstructured":"Jie Gao, Leonidas J. Guibas, and An Nguyen. 2006. Deformable spanners and applications. Comput. Geom. Theory Appl., 35, 1, 2006."},{"key":"e_1_3_2_1_23_1","first-page":"2","article-title":"1995","volume":"24","author":"Goemans Michel X.","year":"1995","unstructured":"Michel X. Goemans and David P. Williamson. 1995. A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput., 24, 2, 1995. Pages 296\u2013317. issn:0097-5397","journal-title":"A General Approximation Technique for Constrained Forest Problems. SIAM J. Comput."},{"key":"e_1_3_2_1_24_1","volume-title":"Fully Dynamic k-Center Clustering in Doubling Metrics. arXiv preprint arXiv:1908.03948","author":"Goranci Gramoz","year":"2019","unstructured":"Gramoz Goranci, Monika Henzinger, Dariusz Leniowski, and Alexander Svozil. 2019. Fully Dynamic k-Center Clustering in Doubling Metrics. arXiv preprint arXiv:1908.03948, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.52"},{"key":"e_1_3_2_1_26_1","series-title":"SIAM J. Comput., 35, 5","volume-title":"Fast Construction of Nets in Low-Dimensional Metrics and Their Applications","author":"Har-Peled Sariel","year":"2006","unstructured":"Sariel Har-Peled and Manor Mendel. 2006. Fast Construction of Nets in Low-Dimensional Metrics and Their Applications. SIAM J. Comput., 35, 5, 2006. Pages 1148\u20131184."},{"key":"e_1_3_2_1_27_1","volume-title":"Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS).","author":"Huang L.","unstructured":"L. Huang, S. H. . Jiang, J. Li, and X. Wu. 2018. Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1107206"},{"key":"e_1_3_2_1_29_1","volume-title":"Lee","author":"Krauthgamer Robert","year":"2004","unstructured":"Robert Krauthgamer and James R. Lee. 2004. Navigating nets: Simple algorithms for proximity search. In 15th Annual ACM-SIAM Symposium on Discrete Algorithms. Pages 791\u2013801."},{"key":"e_1_3_2_1_30_1","series-title":"SIAM J. Comput., 28, 4","volume-title":"Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems","author":"Mitchell Joseph S. B.","year":"1999","unstructured":"Joseph S. B. Mitchell. 1999. Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems. SIAM J. Comput., 28, 4, 1999. Pages 1298\u20131309."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276868"},{"key":"e_1_3_2_1_32_1","volume-title":"On some combinatorial problems in metric spaces of bounded doubling dimension","author":"Smid Michiel","year":"2010","unstructured":"Michiel Smid. 2010. On some combinatorial problems in metric spaces of bounded doubling dimension. 2010."},{"key":"e_1_3_2_1_33_1","volume-title":"36th annual ACM symposium on Theory of computing. ACM. Pages 281\u2013290.","author":"Talwar Kunal","unstructured":"Kunal Talwar. 2004. Bypassing the embedding: algorithms for low dimensional metrics. In 36th annual ACM symposium on Theory of computing. ACM. Pages 281\u2013290."}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy","acronym":"STOC '21","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451063","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":33,"alternative-id":["10.1145\/3406325.3451063","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451063","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}