{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,21]],"date-time":"2026-07-21T09:58:55Z","timestamp":1784627935492,"version":"3.55.0"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2013,9,21]],"date-time":"2013-09-21T00:00:00Z","timestamp":1379721600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2014,9]]},"DOI":"10.1007\/s00453-013-9833-9","type":"journal-article","created":{"date-parts":[[2013,9,20]],"date-time":"2013-09-20T10:44:11Z","timestamp":1379673851000},"page":"22-46","source":"Crossref","is-referenced-by-count":29,"title":["A Simple D 2-Sampling Based PTAS for k-Means and Other Clustering Problems"],"prefix":"10.1007","volume":"70","author":[{"given":"Ragesh","family":"Jaiswal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sandeep","family":"Sen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2013,9,21]]},"reference":[{"key":"9833_CR1","unstructured":"Ackermann, M.R.: Algorithms for the Bregman k-Median Problem. Ph.D. Thesis, University of Paderborn (2010)"},{"key":"9833_CR2","doi-asserted-by":"crossref","first-page":"1088","DOI":"10.1137\/1.9781611973068.118","volume-title":"Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201909","author":"M.R. Ackermann","year":"2009","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Coresets and approximate clustering for Bregman divergences. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201909, pp.\u00a01088\u20131097. SIAM, Philadelphia (2009)"},{"key":"9833_CR3","first-page":"212","volume-title":"Proceedings of the 12th Scandinavian Conference on Algorithm Theory, SWAT\u201910","author":"M.R. Ackermann","year":"2010","unstructured":"Ackermann, M.R., Bl\u00f6mer, J.: Bregman clustering for separable instances. In: Proceedings of the 12th Scandinavian Conference on Algorithm Theory, SWAT\u201910, pp.\u00a0212\u2013223. Springer, Berlin (2010)"},{"key":"9833_CR4","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1145\/1824777.1824779","volume":"6","author":"M.R. Ackermann","year":"2010","unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Sohler, C.: Clustering for metric and nonmetric distance measures. ACM Trans. Algorithms 6, 59 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9833_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science, vol. 5687, pp.\u00a015\u201328. Springer, Berlin (2009)"},{"key":"9833_CR6","first-page":"10","volume-title":"NIPS","author":"N. Ailon","year":"2009","unstructured":"Ailon, N., Jaiswal, R., Monteleoni, C.: Streaming k-means approximation. In: NIPS, pp.\u00a010\u201318 (2009)"},{"key":"9833_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2027216.2027217","volume":"19","author":"D. Arthur","year":"2011","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the k-means method. J. ACM 19, 1 (2011)","journal-title":"J. ACM"},{"key":"9833_CR8","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1145\/1137856.1137880","volume-title":"Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG\u201906","author":"D. Arthur","year":"2006","unstructured":"Arthur, D., Vassilvitskii, S.: How slow is the k-means method? In: Proceedings of the Twenty-Second Annual Symposium on Computational Geometry, SCG\u201906, pp.\u00a0144\u2013153. ACM, New York (2006)"},{"key":"9833_CR9","first-page":"1027","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201907","author":"D. Arthur","year":"2007","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201907, pp.\u00a01027\u20131035. SIAM, Philadelphia (2007)"},{"key":"9833_CR10","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1109\/FOCS.2010.36","volume-title":"Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201910","author":"P. Awasthi","year":"2010","unstructured":"Awasthi, P., Blum, A., Sheffet, O.: Stability yields a PTAS for k-median and k-means clustering. In: Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science, FOCS\u201910, pp.\u00a0309\u2013318. IEEE Comput. Soc., Los Alamitos (2010)"},{"key":"9833_CR11","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1145\/509907.509947","volume-title":"Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC\u201902","author":"M. B\u0101doiu","year":"2002","unstructured":"B\u0101doiu, M., Har-Peled, S., Indyk, P.: Approximate clustering via core-sets. In: Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing, STOC\u201902, pp.\u00a0250\u2013257. ACM, New York (2002)"},{"key":"9833_CR12","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."},{"issue":"8\u201313","key":"9833_CR13","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1016\/S0169-7552(97)00031-7","volume":"29","author":"A.Z. Broder","year":"1997","unstructured":"Broder, A.Z., Glassman, S.C., Manasse, M.S., Zweig, G.: Syntactic clustering of the web. Comput. Netw. ISDN Syst. 29(8\u201313), 1157\u20131166 (1997)","journal-title":"Comput. Netw. ISDN Syst."},{"key":"9833_CR14","first-page":"1177","volume-title":"Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA\u201906","author":"C. Ke","year":"2006","unstructured":"Ke, C.: On k-median clustering in high dimensions. In: Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithm, SODA\u201906, pp.\u00a01177\u20131185. ACM, New York (2006)"},{"key":"9833_CR15","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)"},{"key":"9833_CR16","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1145\/780542.780550","volume-title":"Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC\u201903","author":"W. Fernandez de la Vega","year":"2003","unstructured":"Fernandez de la Vega, W., Karpinski, M., Kenyon, C., Rabani, Y.: Approximation schemes for clustering problems. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC\u201903, pp.\u00a050\u201358. ACM, New York (2003)"},{"key":"9833_CR17","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1002\/(SICI)1097-4571(199009)41:6<391::AID-ASI1>3.0.CO;2-9","volume":"41","author":"S. Deerwester","year":"1990","unstructured":"Deerwester, S., Dumais, S.T., Furnas, G.W., Landauer, T.K., Harshman, A.R.: Indexing by latent semantic analysis. J. Am. Soc. Inf. Sci. 41, 6 (1990)","journal-title":"J. Am. Soc. Inf. Sci."},{"issue":"3\u20134","key":"9833_CR18","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/BF00962238","volume":"3","author":"C. Faloutsos","year":"1994","unstructured":"Faloutsos, C., Barber, R., Flickner, M., Hafner, J., Niblack, W., Petkovic, D., Equitz, W.: Efficient and effective querying by image content. J. Intell. Inf. Syst. 3(3\u20134), 231\u2013262 (1994)","journal-title":"J. Intell. Inf. Syst."},{"key":"9833_CR19","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1145\/1993636.1993712","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC\u201911","author":"D. Feldman","year":"2011","unstructured":"Feldman, D., Langberg, M.: A unified framework for approximating and clustering data. In: Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, STOC\u201911, pp.\u00a0569\u2013578. ACM, New York (2011)"},{"key":"9833_CR20","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1247069.1247072","volume-title":"Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, SCG\u201907","author":"D. Feldman","year":"2007","unstructured":"Feldman, D., Monemizadeh, M., Sohler, C.: A PTAS for k-means clustering based on weak coresets. In: Proceedings of the Twenty-Third Annual Symposium on Computational Geometry, SCG\u201907, pp.\u00a011\u201318. ACM, New York (2007)"},{"key":"9833_CR21","volume-title":"Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201913","author":"D. Feldman","year":"2013","unstructured":"Feldman, D., Schmidt, M., Sohler, C.: Turning big data into tiny data: Constant-size coresets for k-means, PCA and projective clustering. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201913. SIAM, Philadelphia (2013)"},{"key":"9833_CR22","doi-asserted-by":"crossref","first-page":"1343","DOI":"10.1137\/1.9781611973099.106","volume-title":"Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201912","author":"D. Feldman","year":"2012","unstructured":"Feldman, D., Schulman, L.J.: Data reduction for weighted and outlier-resistant clustering. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201912, pp.\u00a01343\u20131354. SIAM, Philadelphia (2012)"},{"key":"9833_CR23","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1145\/1060590.1060622","volume-title":"Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC\u201905","author":"G. Frahling","year":"2005","unstructured":"Frahling, G., Sohler, C.: Coresets in dynamic geometric data streams. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC\u201905, pp.\u00a0209\u2013217. ACM, New York (2005)"},{"key":"9833_CR24","doi-asserted-by":"crossref","first-page":"126","DOI":"10.1145\/1064092.1064114","volume-title":"Proceedings of the Twenty-First Annual Symposium on Computational Geometry, SCG\u201905","author":"S. Har-Peled","year":"2005","unstructured":"Har-Peled, S., Kushal, A.: Smaller coresets for k-median and k-means clustering. In: Proceedings of the Twenty-First Annual Symposium on Computational Geometry, SCG\u201905, pp.\u00a0126\u2013134. ACM, New York (2005)"},{"key":"9833_CR25","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1145\/1007352.1007400","volume-title":"Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC\u201904","author":"S. Har-Peled","year":"2004","unstructured":"Har-Peled, S., Mazumdar, S.: On coresets for k-means and k-median clustering. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC\u201904, pp.\u00a0291\u2013300. ACM, New York (2004)"},{"key":"9833_CR26","first-page":"877","volume-title":"Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201905","author":"S. Har-Peled","year":"2005","unstructured":"Har-Peled, S., Sadri, B.: How fast is the k-means method? In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201905, pp.\u00a0877\u2013885. SIAM, Philadelphia (2005)"},{"key":"9833_CR27","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/177424.178042","volume-title":"Proceedings of the Tenth Annual Symposium on Computational Geometry, SCG\u201994","author":"M. Inaba","year":"1994","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted Voronoi diagrams and randomization to variance-based k-clustering: (extended abstract). In: Proceedings of the Tenth Annual Symposium on Computational Geometry, SCG\u201994, pp.\u00a0332\u2013339. ACM, New York (1994)"},{"issue":"2","key":"9833_CR28","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1667053.1667054","volume":"5","author":"A. Kumar","year":"2010","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 5(2), 1\u201332 (2010)","journal-title":"J. ACM"},{"issue":"2","key":"9833_CR29","doi-asserted-by":"crossref","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 Trans. Inf. Theory 28(2), 129\u2013137 (1982)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9833_CR30","doi-asserted-by":"crossref","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":"9833_CR31","first-page":"1","volume":"28","author":"R. Ostrovsky","year":"2013","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-type methods for the k-means problem. J. ACM 28, 1 (2013)","journal-title":"J. ACM"},{"issue":"1","key":"9833_CR32","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/BF00130487","volume":"7","author":"M. Swain","year":"1991","unstructured":"Swain, M., Ballard, D.: Color indexing. Int. J. Comput. Vis. 7(1), 11\u201332 (1991)","journal-title":"Int. J. Comput. Vis."},{"key":"9833_CR33","doi-asserted-by":"crossref","first-page":"324","DOI":"10.1145\/1542362.1542419","volume-title":"Proceedings of the 25th Annual Symposium on Computational Geometry, SCG\u201909","author":"A. Vattani","year":"2009","unstructured":"Vattani, A.: k-means requires exponentially many iterations even in the plane. In: Proceedings of the 25th Annual Symposium on Computational Geometry, SCG\u201909, pp.\u00a0324\u2013332. ACM, New York (2009)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9833-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-013-9833-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-013-9833-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T09:45:13Z","timestamp":1559123113000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-013-9833-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,21]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,9]]}},"alternative-id":["9833"],"URL":"https:\/\/doi.org\/10.1007\/s00453-013-9833-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,21]]}}}