{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T20:57:36Z","timestamp":1777409856311,"version":"3.51.4"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642002014","type":"print"},{"value":"9783642002021","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-00202-1_24","type":"book-chapter","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T07:34:01Z","timestamp":1234251241000},"page":"274-285","source":"Crossref","is-referenced-by-count":151,"title":["The Planar k-Means Problem is NP-Hard"],"prefix":"10.1007","author":[{"given":"Meena","family":"Mahajan","sequence":"first","affiliation":[]},{"given":"Prajakta","family":"Nimbhorkar","sequence":"additional","affiliation":[]},{"given":"Kasturi","family":"Varadarajan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"24_CR1","unstructured":"Aloise, D., Deshpande, A., Hansen, P., Popat, P.: NP-Hardness of Euclidean Sum-of-Squares Clustering. Technical Report G-2008-33, Les Cahiers du GERAD (to appear in Machine Learning) (April 2008)"},{"key":"24_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1007\/11590156_19","volume-title":"FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science","author":"E. Allender","year":"2005","unstructured":"Allender, E., Datta, S., Roy, S.: The directed planar reachability problem. In: Ramanujam, R., Sen, S. (eds.) FSTTCS 2005. LNCS, vol.\u00a03821, pp. 238\u2013249. Springer, Heidelberg (2005)"},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Arthur, D., Vassilvitskii, S.: Worst-case and smoothed analysis of the ICP algorithm, with an application to the k-means method. In: Proc. IEEE Symp. Foundations of Computer Science (2006)","DOI":"10.1109\/FOCS.2006.79"},{"key":"24_CR4","doi-asserted-by":"crossref","unstructured":"Arthur, D., Vassilvitskii, S.: How slow is the k-means method? In: Proc. Symp. on Comput. Geom. (2006)","DOI":"10.1145\/1137856.1137880"},{"key":"24_CR5","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: The advantages of careful seeding. In: Proc. ACM-SIAM Symp. Discrete Algorithms (2007)"},{"key":"24_CR6","unstructured":"Dasgupta, S.: The hardness of k-means clustering. Technical Report CS2007-0890, University of California, San Diego (2007)"},{"key":"24_CR7","doi-asserted-by":"crossref","unstructured":"de la Vega, F., Karpinski, M., Kenyon, C.: Approximation schemes for clustering problems. In: Proc. ACM Symp. Theory of Computing, pp. 50\u201358 (2003)","DOI":"10.1145\/780542.780550"},{"key":"24_CR8","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1023\/B:MACH.0000033113.59016.96","volume":"56","author":"P. Drineas","year":"2004","unstructured":"Drineas, P., Friexe, A., Kannan, R., Vempala, S., Vinay, V.: Clustering large graphs via the singular value decomposition. Machine Learning\u00a056, 9\u201333 (2004)","journal-title":"Machine Learning"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Gibson, M., Kanade, G., Krohn, E., Pirwani, I., Varadarajan, K.: On clustering to minimize the sum of radii. In: Proc. ACM-SIAM Symp. Discrete Algorithms (2008)","DOI":"10.1007\/s00453-009-9282-7"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Sadri, B.: How fast is the k-means method? In: Proc. ACM-SIAM Symp. Discrete Algorithms, pp. 877\u2013885 (2005)","DOI":"10.1007\/s00453-004-1127-9"},{"key":"24_CR11","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted Voronoi diagrams and randomization to variance-based clustering. In: Proc. Annual Symp. on Comput. Geom., pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"key":"24_CR12","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., Netanyahu, N., Piatko, C., Silverman, R., Wu, A.: A local search approximation algorithm for k-means clustering. Comput. Geom.\u00a028, 89\u2013112 (2004)","journal-title":"Comput. Geom."},{"key":"24_CR13","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1\u2009+\u2009\u03b5) approximation algorithm for k-means clustering in any dimensions. In: Proc. IEEE Symp. Foundations of Computer Science, pp. 454\u2013462 (2004)","DOI":"10.1109\/FOCS.2004.7"},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Leiserson, C.E.: Area-efficient graph layouts (for VLSI). In: Proc. 21st Ann. IEEE Symp. Foundations of Computer Science, pp. 270\u2013281 (1980)","DOI":"10.1109\/SFCS.1980.13"},{"key":"24_CR15","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D. Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput.\u00a011, 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"24_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S. Lloyd","year":"1982","unstructured":"Lloyd, S.: Least squares quantization in PCM. IEEE Transactions on Information Theory\u00a028, 129\u2013136 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"key":"24_CR17","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N. Megiddo","year":"1984","unstructured":"Megiddo, N., Supowit, K.: On the complexity of some common geometric location problems. SIAM J. Comput.\u00a013, 182\u2013196 (1984)","journal-title":"SIAM J. Comput."},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L., Swamy, C.: The effectiveness of Lloyd-type methods for the k-means problem. In: Proc. IEEE Symp. Foundations of Computer Science (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"24_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1109\/TC.1981.6312176","volume":"30","author":"L.G. Valiant","year":"1981","unstructured":"Valiant, L.G.: Universality considerations in VLSI circuits. IEEE Transactions on Computers\u00a030, 135\u2013140 (1981)","journal-title":"IEEE Transactions on Computers"}],"container-title":["Lecture Notes in Computer Science","WALCOM: Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-00202-1_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,7]],"date-time":"2025-02-07T15:23:18Z","timestamp":1738941798000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-00202-1_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642002014","9783642002021"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-00202-1_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}