{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T16:14:26Z","timestamp":1772554466956,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2011,10,1]],"date-time":"2011-10-01T00:00:00Z","timestamp":1317427200000},"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":["J. ACM"],"published-print":{"date-parts":[[2011,10]]},"abstract":"<jats:p>\n            The\n            <jats:italic>k<\/jats:italic>\n            -means method is one of the most widely used clustering algorithms, drawing its popularity from its speed in practice. Recently, however, it was shown to have exponential worst-case running time. In order to close the gap between practical performance and theoretical analysis, the\n            <jats:italic>k<\/jats:italic>\n            -means method has been studied in the model of smoothed analysis. But even the smoothed analyses so far are unsatisfactory as the bounds are still super-polynomial in the number\n            <jats:italic>n<\/jats:italic>\n            of data points.\n          <\/jats:p>\n          <jats:p>\n            In this article, we settle the smoothed running time of the\n            <jats:italic>k<\/jats:italic>\n            -means method. We show that the smoothed number of iterations is bounded by a polynomial in\n            <jats:italic>n<\/jats:italic>\n            and 1\/\n            <jats:italic>\u03c3<\/jats:italic>\n            , where\n            <jats:italic>\u03c3<\/jats:italic>\n            is the standard deviation of the Gaussian perturbations. This means that if an arbitrary input data set is randomly perturbed, then the\n            <jats:italic>k<\/jats:italic>\n            -means method will run in expected polynomial time on that input set.\n          <\/jats:p>","DOI":"10.1145\/2027216.2027217","type":"journal-article","created":{"date-parts":[[2011,10,27]],"date-time":"2011-10-27T13:17:37Z","timestamp":1319721457000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":54,"title":["Smoothed Analysis of the k-Means Method"],"prefix":"10.1145","volume":"58","author":[{"given":"David","family":"Arthur","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bodo","family":"Manthey","sequence":"additional","affiliation":[{"name":"University of Twente"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Heiko","family":"R\u00f6glin","sequence":"additional","affiliation":[{"name":"University of Bonn"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,10]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1088--1097","author":"Ackermann M. R."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1824777.1824779"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.14"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137880"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1027--1035","author":"Arthur D."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683921"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509947"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1046920.1194902"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1050.0170"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.04.004"},{"key":"e_1_2_1_12_1","unstructured":"Berkhin P. 2002. Survey of clustering data mining techniques. Tech. rep. Accrue Software San Jose CA. Berkhin P. 2002. Survey of clustering data mining techniques. Tech. rep. Accrue Software San Jose CA."},{"key":"e_1_2_1_13_1","unstructured":"Duda R. O. Hart P. E. and Stork D. G. 2000. Pattern Classification. John Wiley & Sons. Duda R. O. Hart P. E. and Stork D. G. 2000. Pattern Classification . John Wiley & Sons."},{"key":"e_1_2_1_14_1","volume-title":"Probability: Theory and Examples","author":"Durrett R.","year":"1991"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 1295--1304","author":"Englert M."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.44"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1127-9"},{"key":"e_1_2_1_18_1","first-page":"1199","article-title":"Variance-based k-clustering algorithms by Voronoi diagrams and randomization. IEICE","volume":"6","author":"Inaba M.","year":"2000","journal-title":"Trans. Inf. Syst. E83-D"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2002.1017616"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2004.03.003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.7"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA). 461--470","author":"Manthey B."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_103"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004540010019"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.75"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990310"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-011-9340-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/070683386"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 18th International Conference on Machine Learning (ICML). Morgan Kaufmann, 577--584","author":"Wagstaff K. L."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0226281-1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027217","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2027216.2027217","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:15Z","timestamp":1750278375000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2027216.2027217"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,10]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2011,10]]}},"alternative-id":["10.1145\/2027216.2027217"],"URL":"https:\/\/doi.org\/10.1145\/2027216.2027217","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,10]]},"assertion":[{"value":"2010-01-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}