{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:03Z","timestamp":1750695003936,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":45,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718214","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:24:47Z","timestamp":1750026287000},"page":"665-676","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Near-Optimal Dimension Reduction for Facility Location"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7512-142X","authenticated-orcid":false,"given":"Lingxiao","family":"Huang","sequence":"first","affiliation":[{"name":"Nanjing University, Nanjing, China"}]},{"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\/0009-0008-0515-5446","authenticated-orcid":false,"given":"Di","family":"Yue","sequence":"additional","affiliation":[{"name":"Peking University, Beijing, China"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.24033\/bsmf.1997"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/130913328"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.68"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Luca Becchetti Marc Bury Vincent Cohen-Addad Fabrizio Grandoni and Chris Schwiegelshohn. 2019. Oblivious dimension reduction for k-means: beyond subspaces and the Johnson-Lindenstrauss lemma. In STOC. ACM 1039\u20131050. https:\/\/doi.org\/10.1145\/3313276.3316318 10.1145\/3313276.3316318","DOI":"10.1145\/3313276.3316318"},{"key":"e_1_3_2_1_5_1","volume-title":"Dynamic Facility Location in High Dimensional Euclidean Spaces. In Forty-first International Conference on Machine Learning. https:\/\/openreview.net\/forum?id=rucbIsWoEV","author":"Bhattacharya Sayan","year":"2024","unstructured":"Sayan Bhattacharya, Gramoz Goranci, Shaofeng H.-C. Jiang, Yi Qian, and Yubo Zhang. 2024. Dynamic Facility Location in High Dimensional Euclidean Spaces. In Forty-first International Conference on Machine Learning. https:\/\/openreview.net\/forum?id=rucbIsWoEV"},{"key":"e_1_3_2_1_6_1","volume-title":"NIPS. Curran Associates","author":"Boutsidis Christos","year":"2010","unstructured":"Christos Boutsidis, Anastasios Zouzias, and Petros Drineas. 2010. Random Projections for k-means Clustering. In NIPS. Curran Associates, Inc., 298\u2013306. https:\/\/proceedings.neurips.cc\/paper\/2010\/hash\/73278a4a86960eeb576a8fd4c9ec6997-Abstract.html"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1107206"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3378571"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158232"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.102"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","unstructured":"Xi Chen Vincent Cohen-Addad Rajesh Jayaram Amit Levi and Erik Waingarten. 2023. Streaming Euclidean MST to a Constant Factor. In STOC. ACM 156\u2013169. https:\/\/doi.org\/10.1145\/3564246.3585168 10.1145\/3564246.3585168","DOI":"10.1145\/3564246.3585168"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","unstructured":"Xiaoyu Chen Shaofeng H.-C. Jiang and Robert Krauthgamer. 2023. Streaming Euclidean Max-Cut: Dimension vs Data Reduction. In STOC. ACM 170\u2013182. https:\/\/doi.org\/10.1145\/3564246.3585170 10.1145\/3564246.3585170","DOI":"10.1145\/3564246.3585170"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009449"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Michael B. Cohen Sam Elder Cameron Musco Christopher Musco and Madalina Persu. 2015. Dimensionality Reduction for k-Means Clustering and Low Rank Approximation. In STOC. ACM 163\u2013172. https:\/\/doi.org\/10.1145\/2746539.2746569 10.1145\/2746539.2746569","DOI":"10.1145\/2746539.2746569"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","unstructured":"Vincent Cohen-Addad Hossein Esfandiari Vahab S. Mirrokni and Shyam Narayanan. 2022. Improved approximations for Euclidean k-means and k-median via nested quasi-independent sets. In STOC. ACM 1621\u20131628. https:\/\/doi.org\/10.1145\/3519935.3520011 10.1145\/3519935.3520011","DOI":"10.1145\/3519935.3520011"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3477541"},{"volume-title":"Streaming Facility Location in High Dimension via Geometric Hashing. CoRR, arXiv:2204.02095. The latest version has additional results compared to the preliminary version in CzumajJK0Y22","author":"Czumaj Artur","key":"e_1_3_2_1_17_1","unstructured":"Artur Czumaj, Arnold Filtser, Shaofeng H.-C. Jiang, Robert Krauthgamer, Pavel Vesel\u1ef3, and Mingwei Yang. 2022. Streaming Facility Location in High Dimension via Geometric Hashing. CoRR, arXiv:2204.02095. The latest version has additional results compared to the preliminary version in CzumajJK0Y22"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.50"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00050"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.123"},{"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":"Varadarajan","author":"Goel Ashish","year":"2001","unstructured":"Ashish Goel, Piotr Indyk, and Kasturi R. Varadarajan. 2001. Reductions among high dimensional proximity problems. In SODA. ACM\/SIAM, 769\u2013778. http:\/\/dl.acm.org\/citation.cfm?id=365411.365776"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2339840"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-015-9707-9"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Lingxiao Huang Shaofeng H.-C. Jiang Robert Krauthgamer and Di Yue. 2024. Near-Optimal Dimension Reduction for Facility Location. CoRR arXiv:2411.05432.","DOI":"10.1145\/3717823.3718214"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1147954.1147955"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273340.1273347"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.SoCG.2024.64"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm"},{"key":"e_1_3_2_1_31_1","volume-title":"Approximation and Streaming Algorithms for Projective Clustering via Random Projections","author":"Kerber Michael","year":"2015","unstructured":"Michael Kerber and Sharath Raghvendra. 2015. Approximation and Streaming Algorithms for Projective Clustering via Random Projections. In CCCG. Queen\u2019s University, Ontario, Canada. http:\/\/research.cs.queensu.ca\/cccg2015\/CCCG15-papers\/16.pdf"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702404055"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667054"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03367-4_42"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1012093209450"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.64"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701383443"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0029"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.4171\/RMI"},{"key":"e_1_3_2_1_41_1","volume-title":"ICML (Proceedings of Machine Learning Research","volume":"7957","author":"Narayanan Shyam","year":"2021","unstructured":"Shyam Narayanan, Sandeep Silwal, Piotr Indyk, and Or Zamir. 2021. Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering. In ICML (Proceedings of Machine Learning Research, Vol. 139). PMLR, 7948\u20137957. https:\/\/proceedings.mlr.press\/v139\/narayanan21b.html"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-014-9567-3"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","unstructured":"Kunal Talwar. 2004. Bypassing the embedding: algorithms for low dimensional metrics. In STOC. ACM 281\u2013290. https:\/\/doi.org\/10.1145\/1007352.1007399 10.1145\/1007352.1007399","DOI":"10.1145\/1007352.1007399"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352735"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.78"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718214","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:00Z","timestamp":1750693440000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718214"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":45,"alternative-id":["10.1145\/3717823.3718214","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718214","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}