{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T09:07:09Z","timestamp":1780996029589,"version":"3.54.1"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2009,1,24]],"date-time":"2009-01-24T00:00:00Z","timestamp":1232755200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2009,5]]},"DOI":"10.1007\/s10994-009-5103-0","type":"journal-article","created":{"date-parts":[[2009,1,23]],"date-time":"2009-01-23T11:07:06Z","timestamp":1232708826000},"page":"245-248","source":"Crossref","is-referenced-by-count":650,"title":["NP-hardness of Euclidean sum-of-squares clustering"],"prefix":"10.1007","volume":"75","author":[{"given":"Daniel","family":"Aloise","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Deshpande","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pierre","family":"Hansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Preyas","family":"Popat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,1,24]]},"reference":[{"key":"5103_CR1","unstructured":"Aloise, D., & Hansen, P. (2007). On the complexity of minimum sum-of-squares clustering. Cahiers du GERAD, G-2007-50, July 2007, available online at http:\/\/www.gerad.ca ."},{"key":"5103_CR2","unstructured":"Arthur, D., & Vassilvitskii, S. (2007). K-means++: the advantages of careful seeding. In 2007 ACM-SIAM symposium on discrete algorithms (SODA\u201907)."},{"key":"5103_CR3","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1016\/j.datak.2005.05.009","volume":"58","author":"J. Beringer","year":"2006","unstructured":"Beringer, J., & H\u00fcllermeier, E. (2006). Online clustering of parallel data streams. Data & Knowledge Engineering, 58, 180\u2013204.","journal-title":"Data & Knowledge Engineering"},{"key":"5103_CR4","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1007\/11557067_11","volume":"3692","author":"R. Cilibrasi","year":"2005","unstructured":"Cilibrasi, R., van Iersel, L., Kelk, S., & Tromp, J. (2005). On the complexity of several haplotyping problems. Lecture Notes in Computer Science, 3692, 128\u2013139.","journal-title":"Lecture Notes in Computer Science"},{"key":"5103_CR5","unstructured":"Dasgupta, S. (2008). The hardness of k -means clustering (Technical Report CS2008-0916). University of California, 17 January 2008."},{"key":"5103_CR6","unstructured":"Deshpande, A., & Popat, P. (2008). Email sent to Ravi Kannan et al. and transmitted by Nina Mishra to the first and third authors. 22 January 2008."},{"key":"5103_CR7","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1023\/B:MACH.0000033113.59016.96","volume":"56","author":"P. Drineas","year":"2004","unstructured":"Drineas, P., Frieze, A., Kannan, R., Vempala, S., & Vinay, V. (2004). Clustering large graphs via the singular value decomposition. Machine Learning, 56, 9\u201333.","journal-title":"Machine Learning"},{"key":"5103_CR8","first-page":"191","volume":"79","author":"P. Hansen","year":"1997","unstructured":"Hansen, P., & Jaumard, B. (1997). Cluster analysis and mathematical programming. Mathematical Programming, 79, 191\u2013215.","journal-title":"Mathematical Programming"},{"key":"5103_CR9","unstructured":"Kanade, G., Nimbhorkar, P., & Varadarajan, K. (2008). On the NP-hardness of the 2-means problem. Manuscript of 14 February 2008."},{"key":"5103_CR10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0166-218X(90)90133-W","volume":"27","author":"D. Matula","year":"1990","unstructured":"Matula, D., & Shahrokhi, F. (1990). Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics, 27, 113\u2013123.","journal-title":"Discrete Applied Mathematics"},{"key":"5103_CR11","unstructured":"MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. In Proceedings of 5th Berkeley symposium on mathematical statistics and probability (Vol.\u00a02, pp. 281\u2013297), Berkeley, CA."},{"key":"5103_CR12","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L. J., & Swamy, C. (2006). The effectiveness of Lloyd-type methods for the k-means problem. In Proceedings of the 47th annual IEEE symposium on foundations of computer science (FOCS\u201906).","DOI":"10.1109\/FOCS.2006.75"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-009-5103-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-009-5103-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-009-5103-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T21:40:26Z","timestamp":1559338826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-009-5103-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,24]]},"references-count":12,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["5103"],"URL":"https:\/\/doi.org\/10.1007\/s10994-009-5103-0","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,24]]}}}