{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,16]],"date-time":"2025-12-16T12:37:19Z","timestamp":1765888639378,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":54,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451022","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"169-182","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":16,"title":["A new coreset framework for clustering"],"prefix":"10.1145","author":[{"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4208-8541","authenticated-orcid":false,"given":"David","family":"Saulpic","sequence":"additional","affiliation":[{"name":"Sorbonne University, France \/ CNRS, France \/ LIP6, France"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1202-0805","authenticated-orcid":false,"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[{"name":"Aarhus University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146411"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316318"},{"key":"e_1_3_2_1_3_1","volume-title":"Coresets for clustering in graphs of bounded treewidth","author":"Baker Daniel","year":"2020","unstructured":"Daniel Baker, Vladimir Braverman, Lingxiao Huang, Shaofeng H. C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in graphs of bounded treewidth, 2020."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_3_2_1_5_1","volume-title":"Advances in Neural Information Processing Systems 26:  27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held","author":"Balcan Maria-Florina","year":"2013","unstructured":"Maria-Florina Balcan, Steven Ehrlich, and Yingyu Liang. Distributed k-means and k-median clustering on general communication topologies. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States, pages 1995\u20132003, 2013."},{"key":"e_1_3_2_1_6_1","first-page":"585","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017","author":"Braverman Vladimir","year":"2017","unstructured":"Vladimir Braverman, Gereon Frahling, Harry Lang, Christian Sohler, and Lin F. Yang. Clustering high dimensional dynamic data streams. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 576\u2013585, 2017."},{"key":"e_1_3_2_1_7_1","volume-title":"APPROX\/RANDOM 2019","author":"Braverman Vladimir","year":"2019","unstructured":"Vladimir Braverman, Dan Feldman, Harry Lang, and Daniela Rus. Streaming coreset constructions for m-estimators. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2019, September 20-22, 2019, Massachusetts Institute of Technology, Cambridge, MA, USA, pages 62:1\u201362:15, 2019."},{"key":"e_1_3_2_1_8_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019","author":"Braverman Vladimir","year":"2019","unstructured":"Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for ordered weighted clustering. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, pages 744\u2013753, 2019."},{"key":"e_1_3_2_1_9_1","volume-title":"Coresets for clustering in excluded-minor graphs and beyond. CoRR, abs\/2004.07718","author":"Braverman Vladimir","year":"2020","unstructured":"Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. CoRR, abs\/2004.07718, 2020. Accepted for publication at SODA'21."},{"key":"e_1_3_2_1_10_1","first-page":"2696","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13","author":"Braverman Vladimir","year":"2021","unstructured":"Vladimir Braverman, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Xuan Wu. Coresets for clustering in excluded-minor graphs and beyond. In D\u00e1niel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2679\u20132696. SIAM, 2021."},{"key":"e_1_3_2_1_11_1","series-title":"Proceedings of Machine Learning Research","first-page":"291","volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML","author":"Bachem Olivier","year":"2017","unstructured":"Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause. Uniform deviation bounds for k-means clustering. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 283\u2013291. PMLR, 2017."},{"key":"e_1_3_2_1_12_1","volume-title":"International Conference on Artificial Intelligence and Statistics, AISTATS 2018","author":"Bachem Olivier","year":"2018","unstructured":"Olivier Bachem, Mario Lucic, and Silvio Lattanzi. One-shot coresets: The case of k-clustering. In International Conference on Artificial Intelligence and Statistics, AISTATS 2018, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands, Spain, pages 784\u2013792, 2018."},{"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.1137\/070699007"},{"key":"e_1_3_2_1_15_1","first-page":"14","volume-title":"46th International Colloquium on Automata, Languages, and Programming, ICALP 2019","volume":"132","author":"Cohen-Addad Vincent","year":"2019","unstructured":"Vincent Cohen-Addad and Jason Li. On the fixed-parameter tractability of capacitated clustering. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 41:1\u201341:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019."},{"key":"e_1_3_2_1_16_1","first-page":"81","article-title":"Tight lower bounds on the vc-dimension of geometric set systems","volume":"20","author":"Csik\u00f3s M\u00f3nika","year":"2019","unstructured":"M\u00f3nika Csik\u00f3s, Nabil H. Mustafa, and Andrey Kupavskii. Tight lower bounds on the vc-dimension of geometric set systems. J. Mach. Learn. Res., 20:81:1\u201381:8, 2019.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159719"},{"key":"e_1_3_2_1_18_1","first-page":"14","volume-title":"27th Annual European Symposium on Algorithms, ESA 2019","volume":"144","author":"Cohen-Addad Vincent","year":"2019","unstructured":"Vincent Cohen-Addad, Marcin Pilipczuk, and Michal Pilipczuk. Efficient approximation schemes for uniform-cost clustering problems in planar graphs. In Michael A. Bender, Ola Svensson, and Grzegorz Herman, editors, 27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich\/Garching, Germany, volume 144 of LIPIcs, pages 33:1\u201333:14. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2019."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.14"},{"key":"e_1_3_2_1_20_1","volume-title":"A new coreset framework for clustering. CoRR, abs\/2104.06133","author":"Cohen-Addad Vincent","year":"2021","unstructured":"Vincent Cohen-Addad, David Saulpic, and Chris Schwiegelshohn. A new coreset framework for clustering. CoRR, abs\/2104.06133, 2021."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.10.004"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.06.021"},{"key":"e_1_3_2_1_23_1","first-page":"492","volume-title":"Sophia Antipolis","author":"Fichtenberger Hendrik","year":"2013","unstructured":"Hendrik Fichtenberger, Marc Gill\u00e9, Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. BICO: BIRCH meets coresets for k-means clustering. In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 481\u2013492, 2013."},{"key":"e_1_3_2_1_24_1","volume-title":"Strong coresets for subspace approximation and k-median in nearly linear time. CoRR, abs\/1912.12003","author":"Feng Zhili","year":"2019","unstructured":"Zhili Feng, Praneeth Kacham, and David P. Woodruff. Strong coresets for subspace approximation and k-median in nearly linear time. CoRR, abs\/1912.12003, 2019."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993712"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247072"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060622"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1209854"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238226"},{"key":"e_1_3_2_1_30_1","first-page":"4088","volume-title":"Advances in Neural Information Processing Systems","author":"Huggins Jonathan","year":"2016","unstructured":"Jonathan Huggins, Trevor Campbell, and Tamara Broderick. Coresets for scalable bayesian logistic regression. In Advances in Neural Information Processing Systems, pages 4080\u20134088, 2016."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00082"},{"key":"e_1_3_2_1_32_1","first-page":"7598","volume-title":"Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Huang Lingxiao","year":"2019","unstructured":"Lingxiao Huang, Shaofeng H.-C. Jiang, and Nisheeth K. Vishnoi. Coresets for clustering with fairness constraints. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada, pages 7587\u20137598, 2019."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1271-x"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(99)00216-2"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007400"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384296"},{"key":"e_1_3_2_1_37_1","first-page":"1694","volume-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020","author":"Indyk Piotr","year":"2020","unstructured":"Piotr Indyk, Sepideh Mahabadi, Shayan Oveis Gharan, and Alireza Rezaei. Composable core-sets for determinant maximization problems via spectral spanners. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1675\u20131694. SIAM, 2020."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594560"},{"key":"e_1_3_2_1_39_1","first-page":"896","volume-title":"Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems","author":"Li Yi","year":"2006","unstructured":"Yi Li and Philip M. Long. Learnability and the doubling dimension. In Advances in Neural Information Processing Systems 19, Proceedings of the Twentieth Annual Conference on Neural Information Processing Systems, Vancouver, British Columbia, Canada, December 4-7, 2006, pages 889\u2013896, 2006."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1741"},{"key":"e_1_3_2_1_41_1","first-page":"638","volume-title":"Green Larsen and Jelani Nelson. Optimality of the Johnson-Lindenstrauss Lemma. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017","author":"Kasper","year":"2017","unstructured":"Kasper Green Larsen and Jelani Nelson. Optimality of the Johnson-Lindenstrauss Lemma. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 633\u2013638, 2017."},{"key":"e_1_3_2_1_42_1","first-page":"607","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"Langberg Michael","year":"2010","unstructured":"Michael Langberg and Leonard J. Schulman. Universal $\\varepsilon$-approximators for integrals. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010, pages 598\u2013607, 2010."},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010019"},{"key":"e_1_3_2_1_44_1","first-page":"8318","volume-title":"Advances in Neural Information Processing Systems","author":"Maalouf Alaa","year":"2019","unstructured":"Alaa Maalouf, Ibrahim Jubran, and Dan Feldman. Fast and accurate least-mean-squares solvers. In Advances in Neural Information Processing Systems, pages 8307\u20138318, 2019."},{"key":"e_1_3_2_1_45_1","first-page":"3827","volume-title":"Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18)","author":"Molina Alejandro","year":"2018","unstructured":"Alejandro Molina, Alexander Munteanu, and Kristian Kersting. Core dependency networks. In Sheila A. McIlraith and Kilian Q. Weinberger, editors, Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3820\u20133827. AAAI Press, 2018."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188828"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033114.18632.e0"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13218-017-0519-3"},{"key":"e_1_3_2_1_50_1","first-page":"6571","volume-title":"Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018","author":"Munteanu Alexander","year":"2018","unstructured":"Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, and David P. Woodruff. On coresets for logistic regression. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol\u00f2 Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montr\u00e9al, Canada, pages 6562\u20136571, 2018."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316307"},{"key":"e_1_3_2_1_52_1","volume-title":"Convergence of stochastic processes","author":"Pollard David","year":"2012","unstructured":"David Pollard. Convergence of stochastic processes. Springer Science & Business Media, 2012."},{"key":"e_1_3_2_1_53_1","volume-title":"WAOA 2019","author":"Schmidt Melanie","year":"2019","unstructured":"Melanie Schmidt, Chris Schwiegelshohn, and Christian Sohler. Fair coresets and streaming algorithms for fair k-means. In Approximation and Online Algorithms - 17th International Workshop, WAOA 2019, Munich, Germany, September 12-13, 2019, Revised Selected Papers, pages 232\u2013251, 2019."},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00081"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"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.3451022","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451022"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":54,"alternative-id":["10.1145\/3406325.3451022","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451022","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"}}]}}