{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,25]],"date-time":"2026-09-25T18:53:04Z","timestamp":1790362384403,"version":"4.1.0"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000181","name":"DOD | Air Force Office of Scientific Research (AFOSR)","doi-asserted-by":"publisher","award":["FA9550-09-1-0538"],"award-info":[{"award-number":["FA9550-09-1-0538"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"DOD | Office of Naval Research (ONR)","doi-asserted-by":"publisher","award":["N00014-09-1-0751"],"award-info":[{"award-number":["N00014-09-1-0751"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100004318","name":"Google","doi-asserted-by":"publisher","award":["Google Research Award"],"award-info":[{"award-number":["Google Research Award"]}],"id":[{"id":"10.13039\/100004318","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"Microsoft","doi-asserted-by":"publisher","award":["Microsoft Faculty Fellowship"],"award-info":[{"award-number":["Microsoft Faculty Fellowship"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation (NSF)","doi-asserted-by":"publisher","award":["CCF-0953192"],"award-info":[{"award-number":["CCF-0953192"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006028","name":"National Science Foundation (NSF)","doi-asserted-by":"publisher","award":["CCF-1101283"],"award-info":[{"award-number":["CCF-1101283"]}],"id":[{"id":"10.13039\/100006028","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2016,1]]},"abstract":"<jats:p>Motivated by the fact that distances between data points in many real-world clustering instances are often based on heuristic measures, Bilu and Linial [Proceedings of the Symposium on Innovations in Computer Science, 2010] proposed analyzing objective based clustering problems under the assumption that the optimum clustering to the objective is preserved under small multiplicative perturbations to distances between points. The hope is that by exploiting the structure in such instances, one can overcome worst case hardness results. In this paper, we provide several results within this framework. For center-based objectives, we present an algorithm that can optimally cluster instances resilient to perturbations of factor $(1 + \\sqrt{2})$, solving an open problem of Awasthi, Blum, and Sheffet [Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, 2010]. For $k$-median, a center-based objective of special interest, we additionally give algorithms for a more relaxed assumption in which we allow the optimal solution to change in a small $\\epsilon$ fraction of the points after perturbation. We give the first bounds known for $k$-median under this more realistic and more general assumption. We also provide positive results for min-sum clustering, which is typically a harder objective than center-based objectives from an approximability standpoint. Our algorithms are based on new linkage criteria that may be of independent interest. Additionally, we give sublinear-time algorithms, showing algorithms that can return an implicit clustering from access to only a small random sample.<\/jats:p>","DOI":"10.1137\/140981575","type":"journal-article","created":{"date-parts":[[2016,2,4]],"date-time":"2016-02-04T11:44:19Z","timestamp":1454586259000},"page":"102-155","source":"Crossref","is-referenced-by-count":20,"title":["Clustering under Perturbation Resilience"],"prefix":"10.1137","volume":"45","author":[{"given":"Maria Florina","family":"Balcan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yingyu","family":"Liang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2016,1,28]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"P. Awasthi, A. Blum, and O. Sheffet,\n                      Stability yields a PTAS for $k$-median and $k$-means clustering\n                      , in Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, 2010.","DOI":"10.1109\/FOCS.2010.36"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"atypb4","first-page":"37","author":"Awasthi P.","year":"2012","journal-title":"Berlin"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1145\/2450142.2450144"},{"key":"atypb6","unstructured":"M. F. Balcan and M. Braverman,\n                      Approximate Nash equilibria under stability conditions\n                      , CoRR, abs\/1008.1827, 2010."},{"key":"atypb7","unstructured":"M. F. Balcan and P. Gupta,\n                      Robust hierarchical clustering\n                      , in Proceedings of the Annual Conference on Learning Theory, 2010."},{"key":"atypb8","unstructured":"M.F. Balcan, N. Haghtalab, and C. White,\n                      Symmetric and Asymmetric $k$-Center Clustering under Stability\n                      , preprint, arXiv:1505.03924, 2015."},{"key":"atypb9","unstructured":"Y. Bartal, M. Charikar, and D. Raz,\n                      \n                        Approximating min-sum\n                        k\n                        -clustering in metric spaces\n                      \n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, 2001."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2014.09.025"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2011.tm10183"},{"key":"atypb12","unstructured":"Y. Bilu, A. Daniely, N. Linial, and M. Saks,\n                      On the practically interesting instances of maxcut\n                      , in Proceedings of the International Symposium on Theoretical Aspects of Computer Science, 2013."},{"key":"atypb13","unstructured":"Y. Bilu and N. Linial,\n                      Are stable instances easy?\n                      , in Proceedings of the Symposium on Innovations in Computer Science, 2010."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1882"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"W. F. de la Vega, M. Karpinski, C. Kenyon, and Y. Rabani,\n                      Approximation schemes for clustering problems\n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, 2003.","DOI":"10.1145\/780542.780550"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"C. Dwork and J. Lei,\n                      Differential privacy and robust statistics\n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, 2009.","DOI":"10.1145\/1536414.1536466"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"K. Jain, M. Mahdian, and A. Saberi,\n                      A new greedy approach for facility location problems\n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, 2002.","DOI":"10.1145\/509907.510012"},{"key":"atypb19","doi-asserted-by":"crossref","unstructured":"A. Kumar and R. Kannan,\n                      Clustering with spectral norm and the $k$-means algorithm\n                      , in Proceedings of the IEEE Annual Symposium on Foundations of Computer Science, 2010.","DOI":"10.1109\/FOCS.2010.35"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"S. Li and O. Svensson,\n                      Approximating $k$-median via pseudo-approximation\n                      , in Proceedings of the ACM Symposium on the Theory of Computing, 2013.","DOI":"10.1145\/2488608.2488723"},{"key":"atypb21","unstructured":"R. J. Lipton, E. Markakis, and A. Mehta,\n                      On Stability Properties of Economic Solution Concepts\n                      , manuscript, 2006."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"K. Makarychev, Y. Makarychev, and A. Vijayaraghavan,\n                      Bilu-linial stable instances of max cut and minimum multiway cut\n                      , in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, 2014.","DOI":"10.1137\/1.9781611973402.67"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"K. Makarychev, Y. Makarychev, and A. Vijayaraghavan,\n                      Constant factor approximation for balanced cut in the pie model\n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, 2014.","DOI":"10.1145\/2591796.2591841"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"M. Mihal\u00e1k, M. Sch\u00f6ngens, R. \u0160r\u00e1mek, and P. Widmayer,\n                      On the complexity of the metric TSP under stability considerations\n                      , in Proceedings of the International Conference on Current Trends in Theory and Practice of Computer Science, 2011.","DOI":"10.1007\/978-3-642-18381-2_32"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"K. Nissim, S. Raskhodnikova, and A. Smith,\n                      Smooth sensitivity and sampling in private data analysis\n                      , in Proceedings of the Annual ACM Symposium on Theory of Computing, 2007.","DOI":"10.1145\/1250790.1250803"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, Y. Rabani, L. J. Schulman, and C. Swamy,\n                      The effectiveness of Lloyd-type methods for the $k$-means problem\n                      , in Proceedings of the Annual IEEE Symposium on Foundations of Computer Science, 2006.","DOI":"10.1109\/FOCS.2006.75"},{"key":"atypb27","doi-asserted-by":"crossref","unstructured":"B. Sch\u00f6lkopf and A. J. Smola,\n                      Learning with Kernels\n                      , MIT Press, Cambridge, MA, 2001.","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"atypb28","unstructured":"V. N. Vapnik,\n                      Statistical Learning Theory\n                      , Wiley, New York, 1998."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140981575","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:54:48Z","timestamp":1787338488000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140981575"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,1]]}},"alternative-id":["10.1137\/140981575"],"URL":"https:\/\/doi.org\/10.1137\/140981575","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,1]]}}}