{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T16:01:01Z","timestamp":1725897661970},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642322402"},{"type":"electronic","value":"9783642322419"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-32241-9_2","type":"book-chapter","created":{"date-parts":[[2012,8,13]],"date-time":"2012-08-13T15:12:12Z","timestamp":1344870732000},"page":"13-24","source":"Crossref","is-referenced-by-count":5,"title":["A Simple D 2-Sampling Based PTAS for k-Means and other Clustering Problems"],"prefix":"10.1007","author":[{"given":"Ragesh","family":"Jaiswal","sequence":"first","affiliation":[]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: ACM-SIAM Symposium on Discrete Algorithms, pp. 1027\u20131035 (2007)"},{"key":"2_CR2","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming k-means approximation. In: Advances in Neural Information Processing Systems, vol.\u00a022, pp. 10\u201318 (2009)"},{"key":"2_CR3","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 2009. LNCS, vol.\u00a05687, pp. 15\u201328. Springer, Heidelberg (2009)"},{"key":"2_CR4","unstructured":"Broder, A., Glassman, S., Manasse, M., Zweig, G.: Syntactic clustering of the web"},{"key":"2_CR5","doi-asserted-by":"crossref","unstructured":"Faloutsos, C., Barber, R., Flickner, M., Hafner, J.: Efficient and effective querying by image content. Journal of Intelligent Information Systems (1994)","DOI":"10.1007\/BF00962238"},{"key":"2_CR6","doi-asserted-by":"crossref","unstructured":"Deerwester, S., Dumais, S., Landauer, T., Furnas, G., Harshman, A.: Indexing by latent semantic analysis. Journal of the American Society for Information Science (1990)","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9"},{"key":"2_CR7","doi-asserted-by":"crossref","unstructured":"Swain, M., Ballard, D.: Color indexing. International Journal of Computer Vision (1991)","DOI":"10.1007\/BF00130487"},{"key":"2_CR8","unstructured":"Dasgupta, S.: The hardness of k-means clustering. Technical Report CS2008-0916, Department of Computer Science and Engineering. University of California San Diego (2008)"},{"issue":"2","key":"2_CR9","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\u2013137 (1982)","journal-title":"IEEE Transactions on Information Theory"},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Arthur, D., Vassilvitskii, S.: How slow is the k-means method? In: Proc. 22nd Annual Symposium on Computational Geometry, pp. 144\u2013153 (2006)","DOI":"10.1145\/1137856.1137880"},{"key":"2_CR11","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: Proc. 47th IEEE FOCS, pp. 165\u2013176 (2006)","DOI":"10.1109\/FOCS.2006.75"},{"key":"2_CR12","doi-asserted-by":"crossref","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Coresets and approximate clustering for bregman divergences. In: ACM SIAM Symposium on Discrete Algorithms, pp. 1088\u20131097 (2009)","DOI":"10.1137\/1.9781611973068.118"},{"key":"2_CR13","doi-asserted-by":"crossref","unstructured":"Chen, K.: On k-median clustering in high dimensions. In: SODA, pp. 1177\u20131185 (2006)","DOI":"10.1145\/1109557.1109687"},{"key":"2_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A ptas for k-means clustering based on weak coresets. In: Symposium on Computational Geometry, pp. 11\u201318 (2007)","DOI":"10.1145\/1247069.1247072"},{"key":"2_CR15","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted voronoi diagrams and randomization to variance based k-clustering. In: Proceedings of the Tenth Annual Symposium on Computational Geometry, pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"key":"2_CR16","doi-asserted-by":"crossref","unstructured":"Matousek, J.: On approximate geometric k-clustering. In: Discrete and Computational Geometry (2000)","DOI":"10.1007\/s004540010019"},{"key":"2_CR17","doi-asserted-by":"crossref","unstructured":"Badoiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: STOC, pp. 250\u2013257 (2002)","DOI":"10.1145\/509907.509947"},{"key":"2_CR18","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: ACM Symposium on Theory of Computing, pp. 50\u201358 (2003)","DOI":"10.1145\/780542.780550"},{"key":"2_CR19","doi-asserted-by":"crossref","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: ACM Symposium on Theory of Computing, pp. 291\u2013300 (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"2_CR20","doi-asserted-by":"crossref","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM\u00a057(2) (2010)","DOI":"10.1145\/1667053.1667054"},{"key":"2_CR21","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":"2_CR22","unstructured":"Har-Peled, S., Sadri, B.: How fast is the k-means method? In: ACM SIAM Symposium on Discrete Algorithms, pp. 877\u2013885 (2005)"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-32241-9_2.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:58:49Z","timestamp":1620129529000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-32241-9_2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642322402","9783642322419"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-32241-9_2","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}