{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T05:03:24Z","timestamp":1750309404283,"version":"3.41.0"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,10,31]]},"abstract":"\n We consider a generalization of the Steiner tree problem, the\n Steiner forest problem<\/jats:italic>\n , in the Euclidean plane: the input is a multiset\n \n \\(X\\subseteq{\\mathbb{R}}^{2}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , partitioned into\n \n \\(k\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n color classes\n \n \\(C_{1},\\ldots,C_{k}\\subseteq X\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . The goal is to find a minimum-cost Euclidean graph\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n such that every color class\n \n \\(C_{i}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is connected in\n \n \\(G\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . We study this Steiner forest problem in the streaming setting, where the stream consists of insertions and deletions of points to\n \n \\(X\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n . Each input point\n \n \\(x {\\in} X\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n arrives with its color\n \n \\(\\mathsf{color}(x) {\\in} [k]\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and as usual for dynamic geometric streams, the input is restricted to the discrete grid\n \n \\(\\{1,\\ldots,\\Delta\\}^{2}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n We design a single-pass streaming algorithm that uses\n \n \\(\\operatorname{poly}(k\\cdot\\log\\Delta)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n space and time, and estimates the cost of an optimal Steiner forest solution within ratio arbitrarily close to the famous Euclidean Steiner ratio\n \n \\(\\alpha_{2}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n (currently\n \n \\(1.1547\\leq\\alpha_{2}\\leq 1.214\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n ). This approximation guarantee matches the state-of-the-art bound for streaming Steiner tree, i.e., when\n \n \\(k=1\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , and it is a major open question to improve the ratio to\n \n \\(1+\\varepsilon\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n even for this special case. Our approach relies on a novel combination of streaming techniques, like sampling and linear sketching, with the classical Arora-style dynamic-programming framework for geometric optimization problems, which usually requires large memory and so far has not been applied in the streaming setting.\n <\/jats:p>\n \n We complement our streaming algorithm for the Steiner forest problem with simple arguments showing that any finite multiplicative approximation requires\n \n \\(\\Omega(k)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n bits of space.\n <\/jats:p>","DOI":"10.1145\/3663666","type":"journal-article","created":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T20:09:10Z","timestamp":1715112550000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Streaming Algorithms for Geometric Steiner Forest"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7743-438X","authenticated-orcid":false,"given":"Artur","family":"Czumaj","sequence":"first","affiliation":[{"name":"University of Warwick, Coventry, UK"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7972-827X","authenticated-orcid":false,"given":"Shaofeng H.-C.","family":"Jiang","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-8154-3735","authenticated-orcid":false,"given":"Robert","family":"Krauthgamer","sequence":"additional","affiliation":[{"name":"Weizmann Institute of Science, Rehovot, Israel"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1169-7934","authenticated-orcid":false,"given":"Pavel","family":"Vesel\u00fd","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}]}],"member":"320","published-online":{"date-parts":[[2024,8,5]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-013-9846-4"},{"key":"e_1_3_4_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792236237"},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195903001190"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.25"},{"key":"e_1_3_4_6_1","first-page":"343","volume-title":"Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Andoni Alexandr","year":"2008","unstructured":"Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. 2008. Earth Mover Distance over High-Dimensional Spaces. In Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 343\u2013352. Retrieved from http:\/\/dl.acm.org\/citation.cfm?id=1347082.1347120"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.38"},{"key":"e_1_3_4_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_4_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276718"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1996.548477"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087556.3087585"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-011-9491-8"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2027216.2027219"},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.15"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629654"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305441"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897577"},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1107206"},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1646483.1646578"},{"key":"e_1_3_4_21_1","first-page":"27:1","volume-title":"Proceedings of the 32nd International Symposium on Computational Geometry (SoCG)","author":"Chan Timothy M.","year":"2016","unstructured":"Timothy M. Chan. 2016. Dynamic Streaming Algorithms for \\(\\varepsilon\\) -Kernels. In Proceedings of the 32nd International Symposium on Computational Geometry (SoCG). 27:1\u201327:11."},{"key":"e_1_3_4_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702403244"},{"key":"e_1_3_4_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585168"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519979"},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585170"},{"key":"e_1_3_4_26_1","first-page":"54:1","volume-title":"Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP)","author":"Cheng Kuan","year":"2021","unstructured":"Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, and Yu Zheng. 2021. Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. In Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP). 54:1\u201354:20."},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1985.tb14564.x"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-013-7131-9"},{"key":"e_1_3_4_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780823_22"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.000502204.02095"},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.123"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-014-3035-1"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1105-2"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195908002520"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060622"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0116001"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1283383.1283417"},{"key":"e_1_3_4_39_1","first-page":"31:1","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)","author":"Gro\u00df Martin","year":"2018","unstructured":"Martin Gro\u00df, Anupam Gupta, Amit Kumar, Jannik Matuschke, Daniel R. Schmidt, Melanie Schmidt, and Jos\u00e9 Verschae. 2018. A Local-Search Algorithm for Steiner Forest. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). 31:1\u201331:17."},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746590"},{"key":"e_1_3_4_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/2031416"},{"key":"e_1_3_4_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_4_43_1","unstructured":"Wei Hu Zhao Song Lin F. Yang and Peilin Zhong. 2019. Nearly Optimal Dynamic \\(k\\) -Means Clustering for High-Dimensional Data. arXiv:1802.00459. Retrieved from https:\/\/arxiv.org\/abs\/1802.00459."},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007413"},{"key":"e_1_3_4_45_1","volume-title":"Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision (SCTV)","author":"Indyk Piotr","year":"2003","unstructured":"Piotr Indyk and Nitin Thaper. 2003. Fast Image Retrieval via Embeddings. In Proceedings of the 3rd International Workshop on Statistical and Computational Theories of Vision (SCTV). Retrieved from https:\/\/people.csail.mit.edu\/indyk\/emd.pdf"},{"key":"e_1_3_4_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170004"},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a006"},{"key":"e_1_3_4_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993735"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807094"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000370050018"},{"key":"e_1_3_4_51_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","year":"1997","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press."},{"key":"e_1_3_4_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_42"},{"key":"e_1_3_4_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87744-8_55"},{"key":"e_1_3_4_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3339185"},{"key":"e_1_3_4_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0927-0507(05)80126-4"},{"key":"e_1_3_4_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796309764"},{"key":"e_1_3_4_57_1","doi-asserted-by":"publisher","DOI":"10.1214\/cbms\/1462061091"},{"key":"e_1_3_4_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.122"},{"key":"e_1_3_4_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_402"},{"key":"e_1_3_4_60_1","unstructured":"Christian Sohler. 2012. Problem 52: TSP in the Streaming Model. Retrieved from https:\/\/sublinear.info\/52"},{"key":"e_1_3_4_61_1","first-page":"336","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sun Xiaoming","year":"2007","unstructured":"Xiaoming Sun and David P. Woodruff. 2007. The Communication and Streaming Complexity of Computing the Longest Common and Increasing Subsequences. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 336\u2013345."},{"key":"e_1_3_4_62_1","first-page":"577","volume-title":"Proceedings of the 18th International Conference on Machine Learning (ICML)","author":"Wagstaff Kiri","year":"2001","unstructured":"Kiri Wagstaff, Claire Cardie, Seth Rogers, and Stefan Schr\u00f6dl. 2001. Constrained \\(k\\) -Means Clustering with Background Knowledge. In Proceedings of the 18th International Conference on Machine Learning (ICML). 577\u2013584."},{"key":"e_1_3_4_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.000752204.03790"},{"key":"e_1_3_4_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0510-2"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3663666","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3663666","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:57:59Z","timestamp":1750294679000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3663666"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,5]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,31]]}},"alternative-id":["10.1145\/3663666"],"URL":"https:\/\/doi.org\/10.1145\/3663666","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,8,5]]},"assertion":[{"value":"2022-10-03","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-04-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-08-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}