{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:47Z","timestamp":1787017427870,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":35,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1908347"],"award-info":[{"award-number":["CCF-1908347"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384296","type":"proceedings-article","created":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T17:48:11Z","timestamp":1624902491000},"page":"1416-1429","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":21,"title":["Coresets for clustering in Euclidean spaces: importance sampling is nearly optimal"],"prefix":"10.1145","author":[{"given":"Lingxiao","family":"Huang","sequence":"first","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nisheeth K.","family":"Vishnoi","sequence":"additional","affiliation":[{"name":"Yale University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Pankaj K Agarwal and Cecilia Magdalena Procopiuc. 2002. Exact and approximation algorithms for clustering. Algorithmica 33 2 ( 2002 ) 201-226.  Pankaj K Agarwal and Cecilia Magdalena Procopiuc. 2002. Exact and approximation algorithms for clustering. Algorithmica 33 2 ( 2002 ) 201-226.","DOI":"10.1007\/s00453-001-0110-y"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027-1035","author":"Arthur David","year":"2007","unstructured":"David Arthur and Sergei Vassilvitskii . 2007 . K-means++: The advantages of careful seeding . In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027-1035 . David Arthur and Sergei Vassilvitskii. 2007. K-means++: The advantages of careful seeding. In Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 1027-1035."},{"key":"e_1_3_2_1_3_1","series-title":"SIAM Journal on computing 33, 3 ( 2004 ), 544-562","volume-title":"Local search heuristics for-median and facility location problems","author":"Arya Vijay","unstructured":"Vijay Arya , Naveen Garg , Rohit Khandekar , Adam Meyerson , Kamesh Munagala , and Vinayaka Pandit . 2004. Local search heuristics for-median and facility location problems . SIAM Journal on computing 33, 3 ( 2004 ), 544-562 . Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, and Vinayaka Pandit. 2004. Local search heuristics for-median and facility location problems. SIAM Journal on computing 33, 3 ( 2004 ), 544-562."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310482"},{"key":"e_1_3_2_1_5_1","volume-title":"32nd International Symposium on Computational Geometry (SoCG 2016 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.","author":"Bandyapadhyay Sayan","year":"2016","unstructured":"Sayan Bandyapadhyay and Kasturi Varadarajan . 2016 . On Variants of-means Clustering . In 32nd International Symposium on Computational Geometry (SoCG 2016 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Sayan Bandyapadhyay and Kasturi Varadarajan. 2016. On Variants of-means Clustering. In 32nd International Symposium on Computational Geometry (SoCG 2016 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316318"},{"key":"e_1_3_2_1_7_1","unstructured":"Vladimir Braverman Dan Feldman and Harry Lang. 2016. New Frameworks for Ofline and Streaming Coreset Constructions. CoRR abs\/1612.00889 ( 2016 ).  Vladimir Braverman Dan Feldman and Harry Lang. 2016. New Frameworks for Ofline and Streaming Coreset Constructions. CoRR abs\/1612.00889 ( 2016 )."},{"key":"e_1_3_2_1_8_1","volume-title":"Coresets for Clustering in Graphs of Bounded Treewidth. CoRR abs\/","author":"Braverman Vladimir","year":"1907","unstructured":"Vladimir Braverman , Lingxiao Huang , Shaofeng H.-C. Jiang , Robert Krauthgamer , and Xuan Wu. 2019. Coresets for Clustering in Graphs of Bounded Treewidth. CoRR abs\/ 1907 .04733 ( 2019 ). Vladimir Braverman, Lingxiao Huang, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. 2019. Coresets for Clustering in Graphs of Bounded Treewidth. CoRR abs\/ 1907.04733 ( 2019 )."},{"key":"e_1_3_2_1_9_1","volume-title":"Coresets for Ordered Weighted Clustering. In ICML 2019 : Thirty-sixth International Conference on Machine Learning. 744-753","author":"Braverman Vladimir","year":"2019","unstructured":"Vladimir Braverman , Shaofeng Jiang , Robert Krauthgamer , and Xuan Wu . 2019 . Coresets for Ordered Weighted Clustering. In ICML 2019 : Thirty-sixth International Conference on Machine Learning. 744-753 . Vladimir Braverman, Shaofeng Jiang, Robert Krauthgamer, and Xuan Wu. 2019. Coresets for Ordered Weighted Clustering. In ICML 2019 : Thirty-sixth International Conference on Machine Learning. 744-753."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/070699007"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3305381.3305465"},{"key":"e_1_3_2_1_12_1","volume-title":"Neural networks: Tricks of the trade","author":"Coates Adam","unstructured":"Adam Coates and Andrew Y Ng. 2012. Learning feature representations with-means . In Neural networks: Tricks of the trade . Springer , 561-580. Adam Coates and Andrew Y Ng. 2012. Learning feature representations with-means. In Neural networks: Tricks of the trade. Springer, 561-580."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746569"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746567"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M112717X"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133075"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250884"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973105.103"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Sariel Har-Peled. 2004. Clustering motion. Discrete & Computational Geometry 31 4 ( 2004 ) 545-565.  Sariel Har-Peled. 2004. Clustering motion. Discrete & Computational Geometry 31 4 ( 2004 ) 545-565.","DOI":"10.1007\/s00454-004-2822-7"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_2_1_22_1","volume-title":"Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 814-825","author":"Huang Lingxiao","year":"2018","unstructured":"Lingxiao Huang , Shaofeng Jiang , Jian Li , and Xuan Wu . 2018 . Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 814-825 . Lingxiao Huang, Shaofeng Jiang, Jian Li, and Xuan Wu. 2018. Epsilon-Coresets for Clustering (with Outliers) in Doubling Metrics. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 814-825."},{"key":"e_1_3_2_1_23_1","unstructured":"Lingxiao Huang Shaofeng H.-C. Jiang and Nisheeth Vishnoi. 2019. Coresets for Clustering with Fairness Constraints. In NeurIPS 2019 : Thirty-third Conference on Neural Information Processing Systems. 7589-7600.  Lingxiao Huang Shaofeng H.-C. Jiang and Nisheeth Vishnoi. 2019. Coresets for Clustering with Fairness Constraints. In NeurIPS 2019 : Thirty-third Conference on Neural Information Processing Systems. 7589-7600."},{"key":"e_1_3_2_1_24_1","volume-title":"Some random series of functions","author":"Kahane Csam","unstructured":"Csam Kahane and Jean-Pierre Kahane . 1993. Some random series of functions . Vol. 5 . Cambridge University Press . Csam Kahane and Jean-Pierre Kahane. 1993. Some random series of functions. Vol. 5. Cambridge University Press."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873651"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033114.18632.e0"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Sakib A Mondal. 2018. An improved approximation algorithm for hierarchical clustering. Pattern Recognition Letters 104 ( 2018 ) 23-28.  Sakib A Mondal. 2018. An improved approximation algorithm for hierarchical clustering. Pattern Recognition Letters 104 ( 2018 ) 23-28.","DOI":"10.1016\/j.patrec.2018.01.015"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316307"},{"key":"e_1_3_2_1_31_1","volume-title":"Fair Coresets and Streaming Algorithms for Fair-means. In International Workshop on Approximation and Online Algorithms. 232-251","author":"Schmidt Melanie","year":"2019","unstructured":"Melanie Schmidt , Chris Schwiegelshohn , and Christian Sohler . 2019 . Fair Coresets and Streaming Algorithms for Fair-means. In International Workshop on Approximation and Online Algorithms. 232-251 . Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. 2019. Fair Coresets and Streaming Algorithms for Fair-means. In International Workshop on Approximation and Online Algorithms. 232-251."},{"key":"e_1_3_2_1_32_1","first-page":"532","volume-title":"SODA","volume":"7","author":"Shyamalkumar Nariankadu D","year":"2007","unstructured":"Nariankadu D Shyamalkumar and Kasturi Varadarajan . 2007 . Eficient subspace approximation algorithms . In SODA , Vol. 7 . 532 - 540 . Nariankadu D Shyamalkumar and Kasturi Varadarajan. 2007. Eficient subspace approximation algorithms. In SODA, Vol. 7. 532-540."},{"key":"e_1_3_2_1_33_1","volume-title":"Woodruf","author":"Sohler Christian","year":"2018","unstructured":"Christian Sohler and David P . Woodruf . 2018 . Strong Coresets for-Median and Subspace Approximation: Goodbye Dimension . In FOCS. IEEE Computer Society , 802-813. Christian Sohler and David P. Woodruf. 2018. Strong Coresets for-Median and Subspace Approximation: Goodbye Dimension. In FOCS. IEEE Computer Society, 802-813."},{"key":"e_1_3_2_1_34_1","unstructured":"Pang-Ning Tan Michael Steinbach Vipin Kumar etal 2006. Cluster analysis: basic concepts and algorithms. Introduction to data mining 8 ( 2006 ) 487-568.  Pang-Ning Tan Michael Steinbach Vipin Kumar et al. 2006. Cluster analysis: basic concepts and algorithms. Introduction to data mining 8 ( 2006 ) 487-568."},{"key":"e_1_3_2_1_35_1","unstructured":"Kasturi Varadarajan and Xin Xiao. 2012. On the Sensitivity of Shape Fitting Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.  Kasturi Varadarajan and Xin Xiao. 2012. On the Sensitivity of Shape Fitting Problems. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012 ). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384296","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384296","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:41:12Z","timestamp":1750185672000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384296"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":35,"alternative-id":["10.1145\/3357713.3384296","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384296","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}