{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T02:05:11Z","timestamp":1771985111571,"version":"3.50.1"},"publisher-location":"Cham","reference-count":76,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319494869","type":"print"},{"value":"9783319494876","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-49487-6_3","type":"book-chapter","created":{"date-parts":[[2016,11,10]],"date-time":"2016-11-10T14:11:38Z","timestamp":1478787098000},"page":"81-116","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":63,"title":["Theoretical Analysis of the k-Means Algorithm \u2013 A Survey"],"prefix":"10.1007","author":[{"given":"Johannes","family":"Bl\u00f6mer","sequence":"first","affiliation":[]},{"given":"Christiane","family":"Lammersen","sequence":"additional","affiliation":[]},{"given":"Melanie","family":"Schmidt","sequence":"additional","affiliation":[]},{"given":"Christian","family":"Sohler","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,11,11]]},"reference":[{"key":"3_CR1","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/11503415_31","volume-title":"Learning Theory","author":"D Achlioptas","year":"2005","unstructured":"Achlioptas, D., McSherry, F.: On spectral learning of mixtures of distributions. In: Auer, P., Meir, R. (eds.) COLT 2005. LNCS (LNAI), vol. 3559, pp. 458\u2013469. Springer, Heidelberg (2005). doi: 10.1007\/11503415_31"},{"key":"3_CR2","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Coresets and approximate clustering for Bregman divergences. In: Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pp. 1088\u20131097. Society for Industrial and Applied Mathematics (SIAM) (2009). http:\/\/www.cs.uni-paderborn.de\/uploads\/tx_sibibtex\/CoresetsAndApproximateClusteringForBregmanDivergences.pdf"},{"key":"3_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-642-13731-0_21","volume-title":"Algorithm Theory - SWAT 2010","author":"MR Ackermann","year":"2010","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Bregman clustering for separable instances. In: Kaplan, H. (ed.) SWAT 2010. LNCS, vol. 6139, pp. 212\u2013223. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-13731-0_21"},{"key":"3_CR4","unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Scholz, C.: Hardness and non-approximability of Bregman clustering problems. In: Electronic Colloquium on Computational Complexity (ECCC), vol. 18, no. 15, pp. 1\u201320 (2011). http:\/\/eccc.uni-trier.de\/report\/2011\/015\/ , report no. TR11-015"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Sohler, C.: Clustering for metric and non-metric distance measures. ACM Trans. Algorithms 6(4), Article No. 59:1\u201326 (2010). Special issue on SODA 2008","DOI":"10.1145\/1824777.1824779"},{"key":"3_CR6","unstructured":"Ackermann, M.R., M\u00e4rtens, M., Raupach, C., Swierkot, K., Lammersen, C., Sohler, C.: Streamkm++: a clustering algorithm for data streams. ACM J. Exp. Algorithmics 17, Article No. 4, 1\u201330 (2012)"},{"key":"3_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/978-3-642-03685-9_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A Aggarwal","year":"2009","unstructured":"Aggarwal, A., Deshpande, A., Kannan, R.: Adaptive sampling for k-means clustering. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX\/RANDOM -2009. LNCS, vol. 5687, pp. 15\u201328. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-03685-9_2"},{"key":"3_CR8","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming k-means approximation. In: Proceedings of the 22nd Annual Conference on Neural Information Processing Systems, pp. 10\u201318 (2009)"},{"issue":"2","key":"3_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75(2), 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"key":"3_CR10","unstructured":"Alsabti, K., Ranka, S., Singh, V.: An efficient $$k$$ -means clustering algorithm. In: Proceeding of the First Workshop on High-Performance Data Mining (1998)"},{"issue":"1A","key":"3_CR11","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1214\/105051604000000512","volume":"15","author":"S Arora","year":"2005","unstructured":"Arora, S., Kannan, R.: Learning mixtures of separated nonspherical Gaussians. Ann. Appl. Probab. 15(1A), 69\u201392 (2005)","journal-title":"Ann. Appl. Probab."},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: $$k$$ -means has polynomial smoothed complexity. In: Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2009), pp. 405\u2013414. IEEE Computer Society (2009)","DOI":"10.1109\/FOCS.2009.14"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Arthur, D., Vassilvitskii, S.: How slow is the k-means method? In: Proceedings of the 22nd ACM Symposium on Computational Geometry (SoCG 2006), pp. 144\u2013153 (2006)","DOI":"10.1145\/1137856.1137880"},{"key":"3_CR14","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 1027\u20131035. Society for Industrial and Applied Mathematics (2007)"},{"issue":"2","key":"3_CR15","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/070683921","volume":"39","author":"D Arthur","year":"2009","unstructured":"Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the $$k$$ -means method. SIAM J. Comput. 39(2), 766\u2013782 (2009)","journal-title":"SIAM J. Comput."},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Stability yields a PTAS for k-median and k-means clustering. In: FOCS, pp. 309\u2013318 (2010)","DOI":"10.1109\/FOCS.2010.36"},{"key":"3_CR17","unstructured":"Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A.K.: The hardness of approximation of Euclidean k-means. In: SoCG 2015 (2015, accepted)"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Gupta, A.: Approximate clustering without the approximation. In: SODA, pp. 1068\u20131077 (2009)","DOI":"10.1137\/1.9781611973068.116"},{"issue":"7","key":"3_CR19","doi-asserted-by":"publisher","first-page":"2664","DOI":"10.1109\/TIT.2005.850145","volume":"51","author":"A Banerjee","year":"2005","unstructured":"Banerjee, A., Guo, X., Wang, H.: On the optimality of conditional expectation as a Bregman predictor. IEEE Trans. Inf. Theory 51(7), 2664\u20132669 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"3_CR20","first-page":"1705","volume":"6","author":"A Banerjee","year":"2005","unstructured":"Banerjee, A., Merugu, S., Dhillon, I.S., Ghosh, J.: Clustering with Bregman divergences. J. Mach. Learn. Res. 6, 1705\u20131749 (2005)","journal-title":"J. Mach. Learn. Res."},{"key":"3_CR21","unstructured":"Belkin, M., Sinha, K.: Toward learning Gaussian mixtures with arbitrary separation. In: COLT, pp. 407\u2013419 (2010)"},{"key":"3_CR22","unstructured":"Belkin, M., Sinha, K.: Learning Gaussian mixtures with arbitrary separation. CoRR abs\/0907.1054 (2009)"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Belkin, M., Sinha, K.: Polynomial learning of distribution families. In: FOCS, pp. 103\u2013112 (2010)","DOI":"10.1109\/FOCS.2010.16"},{"key":"3_CR24","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1007\/3-540-28349-8_2","volume-title":"Grouping Multidimensional Data","author":"P Berkhin","year":"2006","unstructured":"Berkhin, P.: A survey of clustering data mining techniques. In: Kogan, J., Nicholas, C., Teboulle, M. (eds.) Grouping Multidimensional Data, pp. 25\u201371. Springer, Heidelberg (2006)"},{"key":"3_CR25","doi-asserted-by":"crossref","unstructured":"Braverman, V., Meyerson, A., Ostrovsky, R., Roytman, A., Shindler, M., Tagiku, B.: Streaming k-means on well-clusterable data. In: SODA, pp. 26\u201340 (2011)","DOI":"10.1137\/1.9781611973082.3"},{"key":"3_CR26","doi-asserted-by":"crossref","unstructured":"Brubaker, S.C., Vempala, S.: Isotropic PCA and affine-invariant clustering. In: FOCS, pp. 551\u2013560 (2008)","DOI":"10.1007\/978-3-540-85221-6_8"},{"key":"3_CR27","unstructured":"Chaudhuri, K., McGregor, A.: Finding metric structure in information theoretic clustering. In: COLT, pp. 391\u2013402. Citeseer (2008)"},{"key":"3_CR28","unstructured":"Chaudhuri, K., Rao, S.: Learning mixtures of product distributions using correlations and independence. In: COLT, pp. 9\u201320 (2008)"},{"issue":"3","key":"3_CR29","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen, K.: On coresets for k-median and k-means clustering in metric and Euclidean spaces and their applications. SIAM J. Comput. 39(3), 923\u2013947 (2009)","journal-title":"SIAM J. Comput."},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Dasgupta, S.: Learning mixtures of Gaussians. In: FOCS, pp. 634\u2013644 (1999)","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"3_CR31","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1007\/978-3-540-45167-9_56","volume-title":"Learning Theory and Kernel Machines","author":"S Dasgupta","year":"2003","unstructured":"Dasgupta, S.: How fast Is k-means? In: Sch\u00f6lkopf, B., Warmuth, M.K. (eds.) COLT-Kernel 2003. LNCS (LNAI), vol. 2777, p. 735. Springer, Heidelberg (2003). doi: 10.1007\/978-3-540-45167-9_56"},{"key":"3_CR32","unstructured":"Dasgupta, S.: The hardness of $$k$$ -means clustering. Technical report CS2008-0916, University of California (2008)"},{"key":"3_CR33","first-page":"203","volume":"8","author":"S Dasgupta","year":"2007","unstructured":"Dasgupta, S., Schulman, L.J.: A probabilistic analysis of EM for mixtures of separated, spherical Gaussians. J. Mach. Learn. Res. 8, 203\u2013226 (2007)","journal-title":"J. Mach. Learn. Res."},{"key":"3_CR34","doi-asserted-by":"crossref","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the 43th Annual ACM Symposium on Theory of Computing (STOC), pp. 569\u2013578 (2011)","DOI":"10.1145\/1993636.1993712"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for $$k$$ -means clustering based on weak coresets. In: Proceedings of the 23rd ACM Symposium on Computational Geometry (SoCG), pp. 11\u201318 (2007)","DOI":"10.1145\/1247069.1247072"},{"issue":"5","key":"3_CR36","doi-asserted-by":"publisher","first-page":"1536","DOI":"10.1137\/060670705","volume":"37","author":"J Feldman","year":"2008","unstructured":"Feldman, J., O\u2019Donnell, R., Servedio, R.A.: Learning mixtures of product distributions over discrete domains. SIAM J. Comput. 37(5), 1536\u20131564 (2008)","journal-title":"SIAM J. Comput."},{"key":"3_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/978-3-642-40450-4_41","volume-title":"Algorithms \u2013 ESA 2013","author":"H Fichtenberger","year":"2013","unstructured":"Fichtenberger, H., Gill\u00e9, M., Schmidt, M., Schwiegelshohn, C., Sohler, C.: BICO: BIRCH meets coresets for k-means clustering. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 481\u2013492. Springer, Heidelberg (2013). doi: 10.1007\/978-3-642-40450-4_41"},{"key":"3_CR38","doi-asserted-by":"crossref","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proceedings of the 37th STOC, pp. 209\u2013217 (2005)","DOI":"10.1145\/1060590.1060622"},{"key":"3_CR39","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1007\/978-3-642-79999-0_3","volume-title":"From Data to Knowledge: Theoretical and Practical Aspects of Classification, Data Analysis, and Knowledge Organization","author":"A Gordon","year":"1996","unstructured":"Gordon, A.: Null models in cluster validation. In: Gaul, W., Pfeifer, D. (eds.) From Data to Knowledge: Theoretical and Practical Aspects of Classification, Data Analysis, and Knowledge Organization, pp. 32\u201344. Springer, Heidelberg (1996)"},{"issue":"3","key":"3_CR40","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1109\/TKDE.2003.1198387","volume":"15","author":"S Guha","year":"2003","unstructured":"Guha, S., Meyerson, A., Mishra, N., Motwani, R., O\u2019Callaghan, L.: Clustering data streams: theory and practice. IEEE Trans. Knowl. Data Eng. 15(3), 515\u2013528 (2003)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"3_CR41","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/978-3-319-09259-1_2","volume-title":"Partitional Clustering Algorithms","author":"G Hamerly","year":"2015","unstructured":"Hamerly, G., Drake, J.: Accelerating Lloyd\u2019s algorithm for k-means clustering. In: Celebi, M.E. (ed.) Partitional Clustering Algorithms, pp. 41\u201378. Springer, Cham (2015)"},{"issue":"1","key":"3_CR42","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00454-006-1271-x","volume":"37","author":"S Har-Peled","year":"2007","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. Discrete Comput. Geom. 37(1), 3\u201319 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"3_CR43","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC 2004), pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"3_CR44","unstructured":"Har-Peled, S., Sadri, B.: How fast is the k-means method? In: SODA, pp. 877\u2013885 (2005)"},{"key":"3_CR45","volume-title":"Clustering Algorithms","author":"JA Hartigan","year":"1975","unstructured":"Hartigan, J.A.: Clustering Algorithms. Wiley, Hoboken (1975)"},{"key":"3_CR46","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering (extended abstract). In: Symposium on Computational Geometry (SoCG 1994), pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"issue":"8","key":"3_CR47","doi-asserted-by":"publisher","first-page":"651","DOI":"10.1016\/j.patrec.2009.09.011","volume":"31","author":"AK Jain","year":"2010","unstructured":"Jain, A.K.: Data clustering: 50 years beyond k-means. Pattern Recogn. Lett. 31(8), 651\u2013666 (2010)","journal-title":"Pattern Recogn. Lett."},{"issue":"3","key":"3_CR48","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1145\/331499.331504","volume":"31","author":"AK Jain","year":"1999","unstructured":"Jain, A.K., Murty, M.N., Flynn, P.J.: Data clustering: a review. ACM Comput. Surv. 31(3), 264\u2013323 (1999)","journal-title":"ACM Comput. Surv."},{"issue":"2","key":"3_CR49","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"issue":"8","key":"3_CR50","doi-asserted-by":"publisher","first-page":"871","DOI":"10.1109\/34.709614","volume":"20","author":"D Judd","year":"1998","unstructured":"Judd, D., McKinley, P.K., Jain, A.K.: Large-scale parallel data clustering. IEEE Trans. Pattern Anal. Mach. Intell. 20(8), 871\u2013876 (1998)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"3_CR51","doi-asserted-by":"crossref","unstructured":"Kalai, A.T., Moitra, A., Valiant, G.: Efficiently learning mixtures of two Gaussians. In: STOC, pp. 553\u2013562 (2010)","DOI":"10.1145\/1806689.1806765"},{"issue":"3\u20134","key":"3_CR52","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1561\/0400000025","volume":"4","author":"R Kannan","year":"2009","unstructured":"Kannan, R., Vempala, S.: Spectral algorithms. Found. Trends Theoret. Comput. Sci. 4(3\u20134), 157\u2013288 (2009)","journal-title":"Found. Trends Theoret. Comput. Sci."},{"issue":"3","key":"3_CR53","doi-asserted-by":"publisher","first-page":"1141","DOI":"10.1137\/S0097539704445925","volume":"38","author":"R Kannan","year":"2008","unstructured":"Kannan, R., Salmasian, H., Vempala, S.: The spectral method for general mixture models. SIAM J. Comput. 38(3), 1141\u20131156 (2008)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"3_CR54","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1109\/TPAMI.2002.1017616","volume":"24","author":"T Kanungo","year":"2002","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: An efficient k-means clustering algorithm: analysis and implementation. IEEE Trans. Pattern Anal. Mach. Intell. 24(7), 881\u2013892 (2002)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"2\u20133","key":"3_CR55","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"T Kanungo","year":"2004","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for $$k$$ -means clustering. Comput. Geom. 28(2\u20133), 89\u2013112 (2004)","journal-title":"Comput. Geom."},{"key":"3_CR56","doi-asserted-by":"crossref","unstructured":"Kumar, A., Kannan, R.: Clustering with spectral norm and the $$k$$ -means algorithm. In: Proceedings of the 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp. 299\u2013308. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.35"},{"key":"3_CR57","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), Article No. 5 (2010)","DOI":"10.1145\/1667053.1667054"},{"key":"3_CR58","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. Bell Laboratories Technical Memorandum (1957)"},{"key":"3_CR59","unstructured":"MacQueen, J.B.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281\u2013297. University of California Press (1967)"},{"key":"3_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-642-00202-1_24","volume-title":"WALCOM: Algorithms and Computation","author":"M Mahajan","year":"2009","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. In: Das, S., Uehara, R. (eds.) WALCOM 2009. LNCS, vol. 5431, pp. 274\u2013285. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-00202-1_24"},{"issue":"1","key":"3_CR61","first-page":"94","volume":"4","author":"B Manthey","year":"2013","unstructured":"Manthey, B., R\u00f6glin, H.: Worst-case and smoothed analysis of k-means clustering with Bregman divergences. JoCG 4(1), 94\u2013132 (2013)","journal-title":"JoCG"},{"key":"3_CR62","doi-asserted-by":"crossref","unstructured":"Manthey, B., R\u00f6lin, H.: Improved smoothed analysis of the k-means method. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 461\u2013470. Society for Industrial and Applied Mathematics (2009)","DOI":"10.1137\/1.9781611973068.51"},{"issue":"1","key":"3_CR63","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s004540010019","volume":"24","author":"J Matou\u0161ek","year":"2000","unstructured":"Matou\u0161ek, J.: On approximate geometric k-clustering. Discrete Comput. Geom. 24(1), 61\u201384 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"3_CR64","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0166-218X(90)90133-W","volume":"27","author":"DW Matula","year":"1990","unstructured":"Matula, D.W., Shahrokhi, F.: Sparsest cuts and bottlenecks in graphs. Discrete Appl. Math. 27, 113\u2013123 (1990)","journal-title":"Discrete Appl. Math."},{"key":"3_CR65","doi-asserted-by":"crossref","unstructured":"Moitra, A., Valiant, G.: Settling the polynomial learnability of mixtures of Gaussians. In: FOCS 2010 (2010)","DOI":"10.1109\/FOCS.2010.15"},{"key":"3_CR66","series-title":"Lecture Notes in Computer Science (Lecture Notes in Artificial Intelligence)","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-87481-2_11","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"R Nock","year":"2008","unstructured":"Nock, R., Luosto, P., Kivinen, J.: Mixed Bregman clustering with approximation guarantees. In: Daelemans, W., Goethals, B., Morik, K. (eds.) ECML PKDD 2008. LNCS (LNAI), vol. 5212, pp. 154\u2013169. Springer, Heidelberg (2008). doi: 10.1007\/978-3-540-87481-2_11"},{"key":"3_CR67","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-type methods for the k-means problem. In: FOCS, pp. 165\u2013176 (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"3_CR68","doi-asserted-by":"crossref","unstructured":"Pelleg, D., Moore, A.W.: Accelerating exact k-means algorithms with geometric reasoning. In: Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 277\u2013281 (1999)","DOI":"10.1145\/312129.312248"},{"issue":"1","key":"3_CR69","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/TPAMI.1984.4767478","volume":"6","author":"SZ Selim","year":"1984","unstructured":"Selim, S.Z., Ismail, M.A.: $$k$$ -means-type algorithms: a generalized convergence theorem and characterization of local optimality. IEEE Trans. Pattern Anal. Mach. Intell. (PAMI) 6(1), 81\u201387 (1984)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell. (PAMI)"},{"issue":"12","key":"3_CR70","first-page":"801","volume":"IV","author":"H Steinhaus","year":"1956","unstructured":"Steinhaus, H.: Sur la division des corps mat\u00e9riels en parties. Bulletin de l\u2019Acad\u00e9mie Polonaise des Sciences IV(12), 801\u2013804 (1956)","journal-title":"Bulletin de l\u2019Acad\u00e9mie Polonaise des Sciences"},{"key":"3_CR71","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1111\/1467-9868.00293","volume":"63","author":"R Tibshirani","year":"2001","unstructured":"Tibshirani, R., Walther, G., Hastie, T.: Estimating the number of clusters in a dataset via the gap statistic. J. R. Stat. Soc. Ser. B (Stat. Methodol.) 63, 411\u2013423 (2001)","journal-title":"J. R. Stat. Soc. Ser. B (Stat. Methodol.)"},{"key":"3_CR72","doi-asserted-by":"crossref","unstructured":"Vattani, A.: $$k$$ -means requires exponentially many iterations even in the plane. In: Proceedings of the 25th ACM Symposium on Computational Geometry (SoCG 2009), pp. 324\u2013332. Association for Computing Machinery (2009)","DOI":"10.1145\/1542362.1542419"},{"key":"3_CR73","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 50\u201358 (2003)","DOI":"10.1145\/780542.780550"},{"issue":"4","key":"3_CR74","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.jcss.2003.11.008","volume":"68","author":"S Vempala","year":"2004","unstructured":"Vempala, S., Wang, G.: A spectral algorithm for learning mixture models. J. Comput. Syst. Sci. 68(4), 841\u2013860 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR75","unstructured":"Venkatasubramanian, S.: Choosing the number of clusters I-III (2010). http:\/\/blog.geomblog.org\/p\/conceptual-view-of-clustering.html . Accessed 30 Mar 2015"},{"issue":"2","key":"3_CR76","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/A:1009783824328","volume":"1","author":"T Zhang","year":"1997","unstructured":"Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: a new data clustering algorithm and its applications. Data Min. Knowl. Disc. 1(2), 141\u2013182 (1997)","journal-title":"Data Min. Knowl. Disc."}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-49487-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,12]],"date-time":"2025-06-12T10:04:21Z","timestamp":1749722661000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-49487-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319494869","9783319494876"],"references-count":76,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-49487-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"11 November 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}