{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T15:30:59Z","timestamp":1772119859767,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":48,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,8,24]],"date-time":"2024-08-24T00:00:00Z","timestamp":1724457600000},"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":[[2024,8,25]]},"DOI":"10.1145\/3637528.3671888","type":"proceedings-article","created":{"date-parts":[[2024,8,25]],"date-time":"2024-08-25T04:55:12Z","timestamp":1724561712000},"page":"29-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Resilient k-Clustering"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4315-2381","authenticated-orcid":false,"given":"Sara","family":"Ahmadian","sequence":"first","affiliation":[{"name":"Google, Seattle, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1814-1293","authenticated-orcid":false,"given":"MohammadHossein","family":"Bateni","sequence":"additional","affiliation":[{"name":"Google, New york, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8130-6631","authenticated-orcid":false,"given":"Hossein","family":"Esfandiari","sequence":"additional","affiliation":[{"name":"Google, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3502-7559","authenticated-orcid":false,"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google, Barcelona, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8459-7822","authenticated-orcid":false,"given":"Morteza","family":"Monemizadeh","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, TU Eindhoven, Eindhoven, Netherlands"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2336-9826","authenticated-orcid":false,"given":"Ashkan","family":"Norouzi-Fard","sequence":"additional","affiliation":[{"name":"Google, Zurich, Switzerland"}]}],"member":"320","published-online":{"date-parts":[[2024,8,24]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2020.8"},{"key":"e_1_3_2_1_2_1","volume-title":"Reddy","author":"Aggarwal Charu C.","year":"2013","unstructured":"Charu C. Aggarwal and Chandan K. Reddy. 2013. Data Clustering: Algorithms and Applications (1st ed.). Chapman Hall\/CRC."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2090236.2090249"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043199"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3381424"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2627435.2750367"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000193"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-022-01799-3"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 2018World WideWeb Conference. 579--587","author":"Hubert Chan TH","year":"2018","unstructured":"TH Hubert Chan, Arnaud Guerqin, and Mauro Sozio. 2018. Fully dynamic kcenter clustering. In Proceedings of the 2018World WideWeb Conference. 579--587."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258657"},{"key":"e_1_3_2_1_12_1","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM","author":"Chekuri Chandra","year":"2018","unstructured":"Chandra Chekuri and Shalmoli Gupta. 2018. Perturbation Resilient Clustering for k-Center and Related Problems via LP Relaxations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2018, August 20--22, 2018 - Princeton, NJ, USA (LIPIcs), Eric Blais, Klaus Jansen, Jos\u00e9 D. P. Rolim, and David Steurer (Eds.), Vol. 116. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 9:1--9:16. https:\/\/doi.org\/10.4230\/ LIPICS.APPROX-RANDOM.2018.9"},{"key":"e_1_3_2_1_13_1","first-page":"493","article-title":"A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations","volume":"23","author":"Chernoff H.","year":"1952","unstructured":"H. Chernoff. 1952. A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations. AMS 23, 4 (1952), 493 -- 507.","journal-title":"AMS"},{"key":"e_1_3_2_1_14_1","volume-title":"Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022","volume":"151","author":"Chierichetti Flavio","year":"2022","unstructured":"Flavio Chierichetti, Alessandro Panconesi, Giuseppe Re, and Luca Trevisan. 2022. Spectral Robustness for Correlation Clustering Reconstruction in Semi-Adversarial Models. In International Conference on Artificial Intelligence and Statistics, AISTATS 2022, 28--30 March 2022, Virtual Event (Proceedings of Machine Learning Research), Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera (Eds.), Vol. 151. PMLR, 10852--10880. https:\/\/proceedings.mlr.press\/v151\/ chierichetti22a.html"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2021.108306"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520011"},{"key":"e_1_3_2_1_17_1","volume-title":"Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn.","author":"Cohen-Addad Vincent","year":"2019","unstructured":"Vincent Cohen-Addad, Niklas Oskar D Hjuler, Nikos Parotsidis, David Saulpic, and Chris Schwiegelshohn. 2019. Fully dynamic consistent facility location. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_3_2_1_18_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press. http:\/\/mitpress.mit. edu\/books\/introduction-algorithms","edition":"3"},{"key":"e_1_3_2_1_19_1","volume-title":"Networks, Crowds, and Markets: Reasoning About a Highly Connected World","author":"David Easley","unstructured":"Easley David and Kleinberg Jon. 2010. Networks, Crowds, and Markets: Reasoning About a Highly Connected World. Cambridge University Press, USA."},{"key":"e_1_3_2_1_20_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265--284."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--662--43951--7_39"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62255"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.158"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718348"},{"key":"e_1_3_2_1_26_1","volume-title":"Clustering to minimize the maximum intercluster distance. Theoretical computer science 38","author":"Gonzalez Teofilo F","year":"1985","unstructured":"Teofilo F Gonzalez. 1985. Clustering to minimize the maximum intercluster distance. Theoretical computer science 38 (1985), 293--306."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224--5"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.2307\/2346439"},{"key":"e_1_3_2_1_29_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 1135--1143","author":"Guo Xiangyu","year":"2021","unstructured":"Xiangyu Guo, Janardhan Kulkarni, Shi Li, and Jiayi Xian. 2021. Consistent k-median: Simpler, better and robust. In International Conference on Artificial Intelligence and Statistics. PMLR, 1135--1143."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-004--2822--7"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446281"},{"key":"e_1_3_2_1_32_1","volume-title":"Average Sensitivity of Decision Tree Learning. In The Eleventh International Conference on Learning Representations.","author":"Hara Satoshi","unstructured":"Satoshi Hara and Yuichi Yoshida. [n.d.]. Average Sensitivity of Decision Tree Learning. In The Eleventh International Conference on Learning Representations."},{"key":"e_1_3_2_1_33_1","volume-title":"A best possible heuristic for the k-center problem. Mathematics of operations research 10, 2","author":"Hochbaum Dorit S","year":"1985","unstructured":"Dorit S Hochbaum and David B Shmoys. 1985. A best possible heuristic for the k-center problem. Mathematics of operations research 10, 2 (1985), 180--184."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2755573.2755607"},{"key":"e_1_3_2_1_35_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2241--2250","author":"Karimi Jaghargh Mohammad Reza","year":"2019","unstructured":"Mohammad Reza Karimi Jaghargh, Andreas Krause, Silvio Lattanzi, and Sergei Vassilvtiskii. 2019. Consistent online optimization: Convex and submodular. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2241--2250."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.77"},{"key":"e_1_3_2_1_37_1","volume-title":"Lipschitz Continuous Algorithms for Graph Problems. arXiv preprint arXiv:2211.04674","author":"Kumabe Soh","year":"2022","unstructured":"Soh Kumabe and Yuichi Yoshida. 2022. Lipschitz Continuous Algorithms for Graph Problems. arXiv preprint arXiv:2211.04674 (2022)."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688104"},{"key":"e_1_3_2_1_39_1","volume-title":"International Conference on Machine Learning. PMLR","author":"Lattanzi Silvio","year":"2017","unstructured":"Silvio Lattanzi and Sergei Vassilvitskii. 2017. Consistent k-clustering. In International Conference on Machine Learning. PMLR, 1975--1984."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540-77004--6_5"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129299"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0076--6879(88)64084--5"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1090\/dimacs\/020\/07"},{"key":"e_1_3_2_1_44_1","volume-title":"The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13--15","volume":"130","author":"Subbaswamy Adarsh","year":"2021","unstructured":"Adarsh Subbaswamy, Roy Adams, and Suchi Saria. 2021. Evaluating Model Robustness and Stability to Dataset Shift. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13--15, 2021, Virtual Event (Proceedings of Machine Learning Research), Arindam Banerjee and Kenji Fukumizu (Eds.), Vol. 130. PMLR, 2611--2619. http:\/\/proceedings.mlr.press\/v130\/ subbaswamy21a.html"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.43"},{"key":"e_1_3_2_1_46_1","unstructured":"Yuichi Yoshida and Shinji Ito. 2022. Average Sensitivity of Euclidean k-Clustering. In Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_47_1","volume-title":"Sensitivity analysis of the maximum matching problem. arXiv preprint arXiv:2009.04556","author":"Yoshida Yuichi","year":"2020","unstructured":"Yuichi Yoshida and Samson Zhou. 2020. Sensitivity analysis of the maximum matching problem. arXiv preprint arXiv:2009.04556 (2020)."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009783824328"}],"event":{"name":"KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining","location":"Barcelona Spain","acronym":"KDD '24","sponsor":["SIGMOD ACM Special Interest Group on Management of Data","SIGKDD ACM Special Interest Group on Knowledge Discovery in Data"]},"container-title":["Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3637528.3671888","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3637528.3671888","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:04:15Z","timestamp":1750291455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3637528.3671888"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,24]]},"references-count":48,"alternative-id":["10.1145\/3637528.3671888","10.1145\/3637528"],"URL":"https:\/\/doi.org\/10.1145\/3637528.3671888","relation":{},"subject":[],"published":{"date-parts":[[2024,8,24]]},"assertion":[{"value":"2024-08-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}