{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T18:00:47Z","timestamp":1772906447086,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642036842","type":"print"},{"value":"9783642036859","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","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-03685-9_2","type":"book-chapter","created":{"date-parts":[[2009,8,21]],"date-time":"2009-08-21T02:39:51Z","timestamp":1250822391000},"page":"15-28","source":"Crossref","is-referenced-by-count":55,"title":["Adaptive Sampling for k-Means Clustering"],"prefix":"10.1007","author":[{"given":"Ankit","family":"Aggarwal","sequence":"first","affiliation":[]},{"given":"Amit","family":"Deshpande","sequence":"additional","affiliation":[]},{"given":"Ravi","family":"Kannan","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"2","key":"2_CR1","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 Eu- clidean sum-of-squares clustering. Machine Learning\u00a075(2), 245\u2013248 (2009)","journal-title":"Machine Learning"},{"key":"2_CR2","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: k-means has polynomial smoothed complexity (2009), http:\/\/arxiv.org\/abs\/0904.1113"},{"key":"2_CR3","doi-asserted-by":"crossref","unstructured":"Arthur, D., Vassilvitskii, S.: How slow is the k-means method?. In: Annual Symposium on Computational Geometry (SOCG) (2006)","DOI":"10.1145\/1137856.1137880"},{"key":"2_CR4","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: The advantages of careful seeding. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2007)"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, M., Shmoys, D.: A constant factor approximation for the k-median problem. Journal of Computer and System Sciences (2002)","DOI":"10.1006\/jcss.2002.1882"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Chen, K.: On coresets for k-median and k-means clustering in metric and euclidean spaces and their applications. Submitted to SIAM Journal on Computing (SICOMP) (2009)","DOI":"10.1137\/070699007"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Charikar, M., O\u2019Callaghan, L., Panigrahy, R.: Better streaming algo- rithms for clustering problems. In: ACM Symposium on Theory of Computing (STOC), pp. 30\u201339 (2003)","DOI":"10.1145\/780542.780548"},{"key":"2_CR8","unstructured":"Dasgupta, S.: The hardness of k-means clustering, Tech. Report CS2008- 0916, UC San Diego (2008)"},{"key":"2_CR9","first-page":"50","volume-title":"ACM Symposium on Theory of Computing (STOC)","author":"F. Vega de la","year":"2003","unstructured":"de la Vega, F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: ACM Symposium on Theory of Computing (STOC), pp. 50\u201358. ACM Press, New York (2003)"},{"key":"2_CR10","unstructured":"Guruswami, V., Indyk, P.: Embeddings and non-approximability of geometric problems. In: ACM-SIAM Symposium on Discrete Algorithms (SODA) (2003)"},{"issue":"3","key":"2_CR11","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.: Clus- tering data streams: Theory and practice. IEEE Transactions on Knowledge and Data Engineering\u00a015(3), 515\u2013528 (2003)","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"2_CR12","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"T. Gonzalez","year":"1985","unstructured":"Gonzalez, T.: Clustering to minimize the maximum intercluster distance. Theoretical Computer Science\u00a038, 293\u2013306 (1985)","journal-title":"Theoretical Computer Science"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On core-sets for k-means and k-median clustering. In: ACM Symposium on Theory of Computing (STOC), pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"2_CR14","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.: Approximation algorithms for metric facility loca- tion and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of ACM\u00a048, 274\u2013296 (2001)","journal-title":"Journal of ACM"},{"issue":"2-3","key":"2_CR15","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","author":"T. Kanugo","year":"2004","unstructured":"Kanugo, T., Mount, D., Netanyahu, N., Piatko, C., Silverman, R., Wu, A.: A local search approximation algorithm for k-means clustering. Computational Geometry\u00a028(2-3), 89\u2013112 (2004)","journal-title":"Computational Geometry"},{"key":"2_CR16","unstructured":"Kanade, G., Nimbhorkar, P., Varadarajan, K.: On the NP-hardness of the 2-means problem (unpublished manuscript) (2008)"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: A simple linear time (1 + \u03b5)- approximation algorithm for k-means clustering in any dimensions. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 454\u2013462 (2004)","DOI":"10.1109\/FOCS.2004.7"},{"issue":"2","key":"2_CR18","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(2), 129\u2013136 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"issue":"1","key":"2_CR19","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 and Computational Geometry\u00a024(1), 61\u201384 (2000)","journal-title":"Discrete and Computational Geometry"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Meyerson, A.: Online facility location. In: IEEE Symposium on Foundations of Computer Science (FOCS) (2001)","DOI":"10.1109\/SFCS.2001.959917"},{"key":"2_CR21","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.\u00a05431, pp. 274\u2013285. Springer, Heidelberg (2009)"},{"key":"2_CR22","unstructured":"Mettu, R., Plaxton, C.: Optimal time bounds for approximate clustering. Machine Learning, 344\u2013351 (2002)"},{"key":"2_CR23","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: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 165\u2013176 (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"2_CR24","doi-asserted-by":"crossref","unstructured":"Vattani, A.: k-means requires exponentially many iterations even in the plane. In: Annual Symposium on Computational Geometry (SOCG) (2009)","DOI":"10.1145\/1542362.1542419"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T20:24:20Z","timestamp":1739305460000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}