{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,24]],"date-time":"2025-10-24T08:21:28Z","timestamp":1761294088449,"version":"3.41.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Sloan Research Fellowship"},{"name":"Bloomberg Data Science research"},{"name":"Microsoft Research Faculty Fellowship"},{"name":"AWS Machine Learning Research Award"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["CCF-1910321, CCF 1535967, CCF-1422910, CCF-145117, and IIS-1618714"],"award-info":[{"award-number":["CCF-1910321, CCF 1535967, CCF-1422910, CCF-145117, and IIS-1618714"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Google Research Award, an IBM Ph.D. fellowship, a National Defense Science 8 Engineering Graduate (NDSEG) fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            The\n            <jats:italic>k<\/jats:italic>\n            -center problem is a canonical and long-studied facility location and clustering problem with many applications in both its symmetric and asymmetric forms. Both versions of the problem have tight approximation factors on worst case instances: a 2-approximation for symmetric\n            <jats:italic>k<\/jats:italic>\n            -center and an\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:sup>*<\/jats:sup>\n            (\n            <jats:italic>k<\/jats:italic>\n            ))-approximation for the asymmetric version. Therefore, to improve on these ratios, one must go beyond the worst case.\n          <\/jats:p>\n          <jats:p>\n            In this work, we take this approach and provide strong positive results both for the asymmetric and symmetric\n            <jats:italic>k<\/jats:italic>\n            -center problems under a natural input stability (promise) condition called\n            <jats:italic>\u03b1-perturbation resilience<\/jats:italic>\n            [15], which states that the optimal solution does not change under any \u03b1-factor perturbation to the input distances. We provide algorithms that give strong guarantees simultaneously for stable and non-stable instances: Our algorithms always inherit the worst-case guarantees of clustering approximation algorithms and output the optimal solution if the input is 2-perturbation resilient. In particular, we show that if the input is only perturbation resilient on part of the data, our algorithm will return the optimal clusters from the region of the data that is perturbation resilient while achieving the best worst-case approximation guarantee on the remainder of the data. Furthermore, we prove that our result is tight by showing symmetric\n            <jats:italic>k<\/jats:italic>\n            -center under (2 \u2212 \u03f5)-perturbation resilience is hard unless\n            <jats:italic>NP<\/jats:italic>\n            =\n            <jats:italic>RP<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            The impact of our results is multifaceted. First, to our knowledge, asymmetric\n            <jats:italic>k<\/jats:italic>\n            -center is the first problem that is hard to approximate to any constant factor in the worst case, yet can be optimally solved in polynomial time under perturbation resilience for a constant value of \u03b1. This is also the first tight result for any problem under perturbation resilience, i.e., this is the first time the exact value of \u03b1 for which the problem switches from being NP-hard to efficiently computable has been found. Furthermore, our results illustrate a surprising relationship between symmetric and asymmetric\n            <jats:italic>k<\/jats:italic>\n            -center instances under perturbation resilience. Unlike approximation ratio, for which symmetric\n            <jats:italic>k<\/jats:italic>\n            -center is easily solved to a factor of 2 but asymmetric\n            <jats:italic>k<\/jats:italic>\n            -center cannot be approximated to any constant factor, both symmetric and asymmetric\n            <jats:italic>k<\/jats:italic>\n            -center can be solved optimally under resilience to 2-perturbations. Finally, our guarantees in the setting where only part of the data satisfies perturbation resilience make these algorithms more applicable to real-life instances.\n          <\/jats:p>","DOI":"10.1145\/3381424","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:33:40Z","timestamp":1583789620000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["<i>k<\/i>\n            -center Clustering under Perturbation Resilience"],"prefix":"10.1145","volume":"16","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nika","family":"Haghtalab","sequence":"additional","affiliation":[{"name":"Cornell University, Ithaca, NY, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Colin","family":"White","sequence":"additional","affiliation":[{"name":"RealityEngines.AI, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055487"},{"volume-title":"Integer Programming and Combinatorial Optimization","author":"Archer Aaron","key":"e_1_2_1_2_1"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.49"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.36"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450144"},{"volume-title":"Proceedings of the Conference on Learning Theory (COLT\u201909)","year":"2009","author":"Balcan Maria-Florina","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2017.v013a013"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/140981575"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04414-4_31"},{"volume-title":"Algorithmic Learning Theory","author":"Ben-David Shalev","key":"e_1_2_1_13_1","doi-asserted-by":"crossref","DOI":"10.1007\/b100989"},{"volume-title":"Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS\u201913)","author":"Bilu Yonatan","key":"e_1_2_1_14_1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000193"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.50"},{"volume-title":"Proceedings of the Symposium on Theory of Computing (STOC\u201999)","author":"Charikar Moses","key":"e_1_2_1_17_1"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201901)","year":"2001","author":"Charikar Moses","key":"e_1_2_1_18_1"},{"volume-title":"Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX-RANDOM\u201918)","year":"2018","author":"Chekuri Chandra","key":"e_1_2_1_19_1"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201908)","year":"2008","author":"Chen Ke","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082038"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.14"},{"volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS\u201919)","year":"2019","author":"Deshpande Amit","key":"e_1_2_1_23_1"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(85)90002-1"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90002-7"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201919)","author":"Friggstad Zachary","key":"e_1_2_1_26_1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(85)90224-5"},{"volume-title":"Proceedings of the Conference on Innovations in Theoretical Computer Science (ITCS\u201914)","author":"Gupta Rishi","key":"e_1_2_1_28_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488650"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.10.2.180"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793304601"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"volume-title":"Complexity of Computer Computations","author":"Karp Richard M.","key":"e_1_2_1_33_1"},{"key":"e_1_2_1_34_1","unstructured":"Jon Kleinberg and Eva Tardos. 2006. Algorithm Design. Pearson Education.  Jon Kleinberg and Eva Tardos. 2006. Algorithm Design. Pearson Education."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"volume-title":"Proceedings of the Symposium on Foundations of Computer Science (FOCS\u201904)","year":"2004","author":"Kumar Amit","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS\u201917)","volume":"1050","author":"Lang Hunter","year":"2017"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.11.009"},{"volume-title":"Proceedings of the International Workshop on Approximation, Randomization, and Combinatorial Optimization Algorithms and Techniques (APPROX-RANDOM\u201916)","year":"2016","author":"Makarychev Konstantin","key":"e_1_2_1_39_1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.67"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2018.01.003"},{"volume-title":"SOFSEM: Theory and Practice of Computer Science","author":"Mihal\u00e1k Mat\u00fa\u0161","key":"e_1_2_1_42_1"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395117"},{"key":"e_1_2_1_44_1","unstructured":"Tim Roughgarden. 2014. Beyond worst-case analysis. Retrieved from: http:\/\/theory.stanford.edu\/ tim\/f14\/f14.html.  Tim Roughgarden. 2014. Beyond worst-case analysis. Retrieved from: http:\/\/theory.stanford.edu\/ tim\/f14\/f14.html."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/22101.22108"},{"volume-title":"Proceedings of the International Conference on Neural Information Processing Systems (NIPS\u201917)","year":"2017","author":"Vijayaraghavan Aravindan","key":"e_1_2_1_47_1"},{"volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA\u201996)","year":"1996","author":"Vishwanathan Sundar","key":"e_1_2_1_48_1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24471-1_14"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381424","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381424","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381424","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:06Z","timestamp":1750199586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381424"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3381424"],"URL":"https:\/\/doi.org\/10.1145\/3381424","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"2019-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}