{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T23:33:54Z","timestamp":1777592034097,"version":"3.51.4"},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2017,11,6]],"date-time":"2017-11-06T00:00:00Z","timestamp":1509926400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2018,1]]},"DOI":"10.1007\/s00224-017-9820-7","type":"journal-article","created":{"date-parts":[[2017,11,5]],"date-time":"2017-11-05T22:16:10Z","timestamp":1509920170000},"page":"93-115","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":28,"title":["Faster Algorithms for the Constrained k-means Problem"],"prefix":"10.1007","volume":"62","author":[{"given":"Anup","family":"Bhattacharya","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ragesh","family":"Jaiswal","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amit","family":"Kumar","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,6]]},"reference":[{"key":"9820_CR1","doi-asserted-by":"crossref","first-page":"59,1","DOI":"10.1145\/1824777.1824779","volume":"6","author":"MR Ackermann","year":"2010","unstructured":"Ackermann, M.R., Bl\u00f6mer, J., Sohler, C.: Clustering for metric and nonmetric distance measures. ACM Trans. Algorithms 6, 59,1\u201359,26 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9820_CR2","doi-asserted-by":"crossref","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. 250\u2013257. ACM, New York (2002)","DOI":"10.1145\/509907.509947"},{"key":"9820_CR3","doi-asserted-by":"crossref","unstructured":"Chen, K.: On k-median clustering in high dimensions. In: Proceedings of the Seventeenth annual ACM-SIAM Symposium on Discrete Algorithm, SODA \u201906, pp. 1177\u20131185. ACM, New York (2006)","DOI":"10.1145\/1109557.1109687"},{"key":"9820_CR4","doi-asserted-by":"crossref","unstructured":"de la Vega, W.F., 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. 50\u201358. ACM, New York (2003)","DOI":"10.1145\/780542.780550"},{"key":"9820_CR5","doi-asserted-by":"crossref","unstructured":"Ding, H., Jinhui, X.: A unified framework for clustering constrained data without locality property. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201915, pp. 1471\u20131490 (2015)","DOI":"10.1137\/1.9781611973730.97"},{"key":"9820_CR6","doi-asserted-by":"crossref","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. 11\u201318. ACM, New York (2007)","DOI":"10.1145\/1247069.1247072"},{"key":"9820_CR7","doi-asserted-by":"crossref","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. 291\u2013300. ACM, New York (2004)","DOI":"10.1145\/1007352.1007400"},{"key":"9820_CR8","doi-asserted-by":"crossref","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. 332\u2013339. ACM, New York (1994)","DOI":"10.1145\/177424.178042"},{"issue":"1","key":"9820_CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/s00453-013-9833-9","volume":"70","author":"R Jaiswal","year":"2014","unstructured":"Jaiswal, R., Kumar, A., Sen, S.: A simple D\n                    2-sampling based PTAS for k-means and other clustering problems. Algorithmica 70(1), 22\u201346 (2014)","journal-title":"Algorithmica"},{"issue":"2","key":"9820_CR10","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/j.ipl.2014.07.009","volume":"115","author":"R Jaiswal","year":"2015","unstructured":"Jaiswal, R., Kumar, M., Yadav, P.: Improved analysis of D\n                    2-sampling based PTAS for k-means and other clustering problems. Inf. Process. Lett. 115(2), 100\u2013103 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9820_CR11","doi-asserted-by":"crossref","first-page":"5,1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar, A., Sabharwal, Y., Sen, S.: Linear-time approximation schemes for clustering problems in any dimensions. J. ACM 57(2), 5,1\u20135,32 (2010)","journal-title":"J. ACM"},{"issue":"1","key":"9820_CR12","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. Discret. Comput. Geom. 24(1), 61\u201384 (2000)","journal-title":"Discret. Comput. Geom."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-017-9820-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9820-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-017-9820-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,1,5]],"date-time":"2018-01-05T01:47:08Z","timestamp":1515116828000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-017-9820-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,11,6]]},"references-count":12,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["9820"],"URL":"https:\/\/doi.org\/10.1007\/s00224-017-9820-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,11,6]]}}}