{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T22:18:49Z","timestamp":1772835529338,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,4,1]],"date-time":"2013-04-01T00:00:00Z","timestamp":1364774400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0953192, CCF-0514922, CCF-0830540, CCF-0448095 and CCF-0729022"],"award-info":[{"award-number":["CCF-0953192, CCF-0514922, CCF-0830540, CCF-0448095 and CCF-0729022"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,4]]},"abstract":"<jats:p>\n            A common approach to clustering data is to view data objects as points in a metric space, and then to optimize a natural distance-based objective such as the\n            <jats:italic>k<\/jats:italic>\n            -median,\n            <jats:italic>k<\/jats:italic>\n            -means, or min-sum score. For applications such as clustering proteins by function or clustering images by subject, the implicit hope in taking this approach is that the optimal solution for the chosen objective will closely match the desired \u201ctarget\u201d clustering (e.g., a correct clustering of proteins by function or of images by who is in them). However, most distance-based objectives, including those mentioned here, are NP-hard to optimize. So, this assumption by itself is not sufficient, assuming P \u2260 NP, to achieve clusterings of low-error via polynomial time algorithms.\n          <\/jats:p>\n          <jats:p>\n            In this article, we show that we can bypass this barrier if we slightly extend this assumption to ask that for some small constant\n            <jats:italic>c<\/jats:italic>\n            , not only the optimal solution, but also all\n            <jats:italic>c<\/jats:italic>\n            -approximations to the optimal solution, differ from the target on at most some \u03f5 fraction of points\u2014we call this\n            <jats:italic>(c,\u03f5)-approximation-stability<\/jats:italic>\n            . We show that under this condition, it is possible to efficiently obtain low-error clusterings even if the property holds only for values\n            <jats:italic>c<\/jats:italic>\n            for which the objective is known to be NP-hard to approximate. Specifically, for any constant\n            <jats:italic>c &gt; 1, (c,\u03f5)<\/jats:italic>\n            -approximation-stability of\n            <jats:italic>k<\/jats:italic>\n            -median or\n            <jats:italic>k<\/jats:italic>\n            -means objectives can be used to efficiently produce a clustering of error\n            <jats:italic>O<\/jats:italic>\n            (\u03f5) with respect to the target clustering, as can stability of the min-sum objective if the target clusters are sufficiently large. Thus, we can perform nearly as well in terms of agreement with the target clustering\n            <jats:italic>as if<\/jats:italic>\n            we could approximate these objectives to this NP-hard value.\n          <\/jats:p>","DOI":"10.1145\/2450142.2450144","type":"journal-article","created":{"date-parts":[[2013,5,1]],"date-time":"2013-05-01T19:47:09Z","timestamp":1367437629000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":25,"title":["Clustering under approximation stability"],"prefix":"10.1145","volume":"60","author":[{"given":"Maria-Florina","family":"Balcan","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology, Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avrim","family":"Blum","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anupam","family":"Gupta","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 10th Annual Conference on Theory and Applications of Models of Computation (TAMC'13)","author":"Agarwal M.","unstructured":"Agarwal , M. , Jaiswal , R. , and Pal , A . 2013. k-means&plus;&plus; under approximation stability . In Proceedings of the 10th Annual Conference on Theory and Applications of Models of Computation (TAMC'13) . Agarwal, M., Jaiswal, R., and Pal, A. 2013. k-means&plus;&plus; under approximation stability. In Proceedings of the 10th Annual Conference on Theory and Applications of Models of Computation (TAMC'13)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055581"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 41st Annual Symposium on Foundations of Computer Science.","author":"Alon N.","unstructured":"Alon , N. , Dar , S. , Parnas , M. , and Ron , D . 2000. Testing of clustering . In Proceedings of the 41st Annual Symposium on Foundations of Computer Science. Alon, N., Dar, S., Parnas, M., and Ron, D. 2000. Testing of clustering. In Proceedings of the 41st Annual Symposium on Foundations of Computer Science."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380808"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276718"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007355"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of SODA. 1027--1035","author":"Arthur D.","unstructured":"Arthur , D. and Vassilvitskii , S . 2007. k-means&plus;&plus;: The advantages of careful seeding . In Proceedings of SODA. 1027--1035 . Arthur, D. and Vassilvitskii, S. 2007. k-means&plus;&plus;: The advantages of careful seeding. In Proceedings of SODA. 1027--1035."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.36"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2011.10.006"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the APPROX-RANDOM. 37--49","author":"Awasthi P.","unstructured":"Awasthi , P. and Sheffet , O . 2012. Improved spectral-norm bounds for clustering . In Proceedings of the APPROX-RANDOM. 37--49 . Awasthi, P. and Sheffet, O. 2012. Improved spectral-norm bounds for clustering. In Proceedings of the APPROX-RANDOM. 37--49."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 22nd Annual Conference on Learning Theory.","author":"Balcan M. F.","year":"2009","unstructured":"Balcan , M. F. 2009 . Better guarantees for sparsest cut clustering . In Proceedings of the 22nd Annual Conference on Learning Theory. Balcan, M. F. 2009. Better guarantees for sparsest cut clustering. In Proceedings of the 22nd Annual Conference on Learning Theory."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms.","author":"Balcan M.-F.","unstructured":"Balcan , M.-F. , Blum , A. , and Gupta , A . 2009a. Approximate clustering without the approximation . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms. Balcan, M.-F., Blum, A., and Gupta, A. 2009a. Approximate clustering without the approximation. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374474"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 22nd Annual Conference on Learning Theory.","author":"Balcan M.-F.","unstructured":"Balcan , M.-F. and Braverman , M . 2009. Finding low error clusterings . In Proceedings of the 22nd Annual Conference on Learning Theory. Balcan, M.-F. and Braverman, M. 2009. Finding low error clusterings. In Proceedings of the 22nd Annual Conference on Learning Theory."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 20th International Conference on Algorithmic Learning Theory.","author":"Balcan M.-F.","unstructured":"Balcan , M.-F. , Roeglin , H. , and Teng , S . 2009b. Agnostic clustering . In Proceedings of the 20th International Conference on Algorithmic Learning Theory. Balcan, M.-F., Roeglin, H., and Teng, S. 2009b. Agnostic clustering. In Proceedings of the 20th International Conference on Algorithmic Learning Theory."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_6"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380754"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"e_1_2_1_21_1","unstructured":"Bilu Y. and Linial N. 2009. Are stable instances easy&quest; CoRR abs\/0906.3162 (2009).  Bilu Y. and Linial N. 2009. Are stable instances easy&quest; CoRR abs\/0906.3162 (2009)."},{"key":"e_1_2_1_22_1","unstructured":"Bilu Y. and Linial N. 2010. Are stable instances easy&quest; In Proceedings of the 1st Symposium on Innovations in Computer Science.  Bilu Y. and Linial N. 2010. Are stable instances easy&quest; In Proceedings of the 1st Symposium on Innovations in Computer Science."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-488"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 40th Annual Symposium on Foundations of Computer Science.","author":"Charikar M.","unstructured":"Charikar , M. and Guha , S . 1999. Improved combinatorial algorithms for the facility location and k-median problems . In Proceedings of the 40th Annual Symposium on Foundations of Computer Science. Charikar, M. and Guha, S. 1999. Improved combinatorial algorithms for the facility location and k-median problems. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301257"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science.","author":"Czumaj A.","unstructured":"Czumaj , A. and Sohler , C . 2007. Small space representations for metric min-sum k-clustering and their applications . In Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science. Czumaj, A. and Sohler, C. 2007. Small space representations for metric min-sum k-clustering and their applications. In Proceedings of the 24th International Symposium on Theoretical Aspects of Computer Science."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796496"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Devroye L. Gyorfi L. and Lugosi G. 1996. A Probabilistic Theory of Pattern Recognition. Springer-Verlag.  Devroye L. Gyorfi L. and Lugosi G. 1996. A Probabilistic Theory of Pattern Recognition. Springer-Verlag.","DOI":"10.1007\/978-1-4612-0711-5"},{"key":"e_1_2_1_30_1","unstructured":"Duda R. O. Hart P. E. and Stork D. G. 2001. Pattern Classification. Wiley.   Duda R. O. Hart P. E. and Stork D. G. 2001. Pattern Classification. Wiley."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780550"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkp985"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/227683.227684"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142400"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0993"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301366"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_30"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the Neural Information Processing Systems.","author":"Kleinberg J.","year":"2002","unstructured":"Kleinberg , J. 2002 . An impossibility theorem for clustering . In Proceedings of the Neural Information Processing Systems. Kleinberg, J. 2002. An impossibility theorem for clustering. In Proceedings of the Neural Information Processing Systems."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_2_1_45_1","unstructured":"Li S. and Svensson O. 2012. Approximating k-Median via Pseudo-Approximation. CoRR abs\/1211.0243 (2012).  Li S. and Svensson O. 2012. Approximating k -Median via Pseudo-Approximation. CoRR abs\/1211.0243 (2012)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"Manning C. D. Raghavan P. and Sch\u00fctze H. 2008. Introduction to Information Retrieval. Cambridge University Press.   Manning C. D. Raghavan P. and Sch\u00fctze H. 2008. Introduction to Information Retrieval. Cambridge University Press.","DOI":"10.1017\/CBO9780511809071"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213014"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_14"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1102351.1102424"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143923"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-011-5267-2"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80134-2"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.75"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/321958.321975"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.5555\/1886811.1886824"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335373"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2003.11.008"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence.","author":"Voevodski K.","unstructured":"Voevodski , K. , Balcan , M.-F. , Roeglin , H. , Teng , S. , and Xia , Y . 2010. Efficient clustering with limited distance information . In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence. Voevodski, K., Balcan, M.-F., Roeglin, H., Teng, S., and Xia, Y. 2010. Efficient clustering with limited distance information. In Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence."},{"key":"e_1_2_1_62_1","unstructured":"Voevodski K. Balcan M.-F. Roeglin H. Teng S. and Xia Y. 2012. Active clustering of biological sequences. J. Mach. Learn. Res.   Voevodski K. Balcan M.-F. Roeglin H. Teng S. and Xia Y. 2012. Active clustering of biological sequences. J. Mach. Learn. Res."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557118"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450144","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2450142.2450144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:49Z","timestamp":1750234729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2450142.2450144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,4]]},"references-count":63,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4]]}},"alternative-id":["10.1145\/2450142.2450144"],"URL":"https:\/\/doi.org\/10.1145\/2450142.2450144","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4]]},"assertion":[{"value":"2010-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}