{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:19:43Z","timestamp":1740122383531,"version":"3.37.3"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T00:00:00Z","timestamp":1628208000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T00:00:00Z","timestamp":1628208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,4]]},"DOI":"10.1007\/s10878-021-00790-6","type":"journal-article","created":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T16:02:42Z","timestamp":1628265762000},"page":"528-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Linear-size universal discretization of geometric center-based problems in fixed dimensions"],"prefix":"10.1007","volume":"43","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4692-1994","authenticated-orcid":false,"given":"Vladimir","family":"Shenmaier","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,6]]},"reference":[{"issue":"2","key":"790_CR1","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1007\/s00453-001-0110-y","volume":"33","author":"P Agarwal","year":"2002","unstructured":"Agarwal P, Procopiuc C (2002) Exact and approximation algorithms for clustering. Algorithmica 33(2):201\u2013226. https:\/\/doi.org\/10.1007\/s00453-001-0110-y","journal-title":"Algorithmica"},{"key":"790_CR2","unstructured":"Agarwal P, Har-Peled S, Varadarajan K (2005) Geometric approximation via coresets. In: Goodman JE, Pach J, Welzl E (eds) Combinatorial and computational geometry, vol 52. Cambridge University Press, Cambridge, pp 1\u201330. http:\/\/library.msri.org\/books\/Book52\/files\/01agar.pdf"},{"issue":"1","key":"790_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/0196-6774(91)90022-Q","volume":"12","author":"A Aggarwal","year":"1991","unstructured":"Aggarwal A, Imai H, Katoh N, Suri S (1991) Finding $$k$$ points with minimum diameter and related problems. J Algorithms 12(1):38\u201356. https:\/\/doi.org\/10.1016\/0196-6774(91)90022-Q","journal-title":"J Algorithms"},{"key":"790_CR4","doi-asserted-by":"crossref","unstructured":"Alon N, Lee T, Shraibman A, Vempala S (2013a) The approximate rank of a matrix and its algorithmic applications. Extended version of the STOC\u00a02013 paper. https:\/\/www.cc.gatech.edu\/~vempala\/papers\/epsrank.pdf","DOI":"10.1145\/2488608.2488694"},{"key":"790_CR5","doi-asserted-by":"publisher","unstructured":"Alon N, Lee T, Shraibman A, Vempala S (2013b) The approximate rank of a matrix and its algorithmic applications. In: Proceedings of 45th ACM symposium on theory of computing (STOC 2013), pp 675\u2013684. https:\/\/doi.org\/10.1145\/2488608.2488694","DOI":"10.1145\/2488608.2488694"},{"key":"790_CR6","doi-asserted-by":"publisher","unstructured":"Arora S, Raghavan P, Rao S (1998) Approximation schemes for Euclidean $$k$$-medians and related problems. In: Proceedings of 30th ACM symposium on theory of computing (STOC 1998), pp 106\u2013113. https:\/\/doi.org\/10.1145\/276698.276718","DOI":"10.1145\/276698.276718"},{"key":"790_CR7","doi-asserted-by":"publisher","unstructured":"B\u01cedoiu M, Har-Peled S, Indyk P (2002) Approximate clustering via core-sets. In: Proceedings of 34th ACM symposium on theory of computing (STOC 2002), pp 250\u2013257. https:\/\/doi.org\/10.1145\/509907.509947","DOI":"10.1145\/509907.509947"},{"issue":"1","key":"790_CR8","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1145\/200836.200853","volume":"42","author":"P Callahan","year":"1995","unstructured":"Callahan P, Kosaraju S (1995) A decomposition of multidimensional point sets with applications to $$k$$-nearest-neighbors and $$n$$-body potential fields. J ACM 42(1):67\u201390. https:\/\/doi.org\/10.1145\/200836.200853","journal-title":"J ACM"},{"key":"790_CR9","doi-asserted-by":"publisher","unstructured":"Chen K (2006) On $$k$$-median clustering in high dimensions. In: Proceedings of 17th ACM-SIAM symposium on discrete algorithms (SODA 2006), pp 1177\u20131185. https:\/\/doi.org\/10.5555\/1109557.1109687","DOI":"10.5555\/1109557.1109687"},{"issue":"3","key":"790_CR10","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/BF02574012","volume":"11","author":"D Eppstein","year":"1994","unstructured":"Eppstein D, Erickson J (1994) Iterated nearest neighbors and finding minimal polytopes. Disc Comput Geom 11(3):321\u2013350. https:\/\/doi.org\/10.1007\/BF02574012","journal-title":"Disc Comput Geom"},{"issue":"5","key":"790_CR11","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled S, Mendel M (2006) Fast construction of nets in low-dimensional metrics and their applications. SIAM J Comput 35(5):1148\u20131184. https:\/\/doi.org\/10.1137\/S0097539704446281","journal-title":"SIAM J Comput"},{"key":"790_CR12","doi-asserted-by":"publisher","unstructured":"Har-Peled S, Mazumdar S (2004) On coresets for $$k$$-means and $$k$$-median clustering. In: Proceedings 36th ACM symposium on theory of computing (STOC 2004), pp 291\u2013300. https:\/\/doi.org\/10.1145\/1007352.1007400","DOI":"10.1145\/1007352.1007400"},{"issue":"1","key":"790_CR13","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1007\/s00453-013-9833-9","volume":"70","author":"R Jaiswal","year":"2014","unstructured":"Jaiswal R, Kumar A, Sen S (2014) A simple $$D^2$$-sampling based PTAS for $$k$$-means and other clustering problems. Algorithmica 70(1):22\u201346. https:\/\/doi.org\/10.1007\/s00453-013-9833-9","journal-title":"Algorithmica"},{"issue":"1","key":"790_CR14","doi-asserted-by":"publisher","first-page":"136","DOI":"10.1134\/S0081543818090146","volume":"303","author":"A Kelmanov","year":"2018","unstructured":"Kelmanov A, Motkova A, Shenmaier V (2018) Approximation scheme for the problem of weighted $$2$$-clustering with a fixed center of one cluster. Proc Steklov Inst Math 303(1):136\u2013145. https:\/\/doi.org\/10.1134\/S0081543818090146","journal-title":"Proc Steklov Inst Math"},{"key":"790_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/996546.996548","volume":"8","author":"P Kumar","year":"2003","unstructured":"Kumar P, Mitchell J, Y\u0131ld\u0131r\u0131m E (2003) Approximate minimum enclosing balls in high dimensions using core-sets. J Exp Algorithmics 8:1\u201329. https:\/\/doi.org\/10.1145\/996546.996548","journal-title":"J Exp Algorithmics"},{"issue":"2","key":"790_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1667053.1667054","volume":"57","author":"A Kumar","year":"2010","unstructured":"Kumar A, Sabharwal Y, Sen S (2010) Linear-time approximation schemes for clustering problems in any dimensions. J ACM 57(2):1\u201332. https:\/\/doi.org\/10.1145\/1667053.1667054","journal-title":"J ACM"},{"issue":"1","key":"790_CR17","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s004540010019","volume":"24","author":"J Matou\u0161ek","year":"2000","unstructured":"Matou\u0161ek J (2000) On approximate geometric $$k$$-clustering. Discrete Comput Geom 24(1):61\u201384. https:\/\/doi.org\/10.1007\/s004540010019","journal-title":"Discrete Comput Geom"},{"issue":"B","key":"790_CR18","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.tcs.2016.10.001","volume":"657","author":"A Meira","year":"2017","unstructured":"Meira A, Miyazawa F, Pedrosa L (2017) Clustering through continuous facility location problems. Theor Comput Sci 657(B):137\u2013145. https:\/\/doi.org\/10.1016\/j.tcs.2016.10.001","journal-title":"Theor Comput Sci"},{"key":"790_CR19","doi-asserted-by":"publisher","unstructured":"Shenmaier V (2019) A structural theorem for center-based clustering in high-dimensional Euclidean space. In: Proceedings of 5th conference on machine learning, optimization, and data science (LOD 2019), LNCS 11943, pp 284\u2013295. https:\/\/doi.org\/10.1007\/978-3-030-37599-7_24","DOI":"10.1007\/978-3-030-37599-7_24"},{"key":"790_CR20","doi-asserted-by":"publisher","unstructured":"Shenmaier V (2020) Some estimates on the discretization of geometric center-based problems in high dimensions. In: Proceedings of 19th conference mathematical optimization theory and operations research (MOTOR 2020). CCIS 127, pp 88\u2013101. https:\/\/doi.org\/10.1007\/978-3-030-58657-7_10","DOI":"10.1007\/978-3-030-58657-7_10"},{"issue":"3","key":"790_CR21","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1134\/S1990478912030131","volume":"6","author":"V Shenmaier","year":"2012","unstructured":"Shenmaier V (2012) An approximation scheme for a problem of search for a vector subset. J Appl Industr Math 6(3):381\u2013386. https:\/\/doi.org\/10.1134\/S1990478912030131","journal-title":"J Appl Industr Math"},{"key":"790_CR22","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/j.ejc.2015.02.011","volume":"48","author":"V Shenmaier","year":"2015","unstructured":"Shenmaier V (2015) Complexity and approximation of the smallest $$k$$-enclosing ball problem. Eur J Comb 48:81\u201387. https:\/\/doi.org\/10.1016\/j.ejc.2015.02.011","journal-title":"Eur J Comb"},{"key":"790_CR23","doi-asserted-by":"publisher","first-page":"53.1","DOI":"10.1201\/9781420010749-63","volume-title":"Handbook of approximation algorithms and metaheuristics","author":"M Smid","year":"2007","unstructured":"Smid M (2007) The well-separated pair decomposition and its applications. In: Gonzalez TF (ed) Handbook of approximation algorithms and metaheuristics. Taylor & Francis, New York, pp 53.1\u201353.12. https:\/\/doi.org\/10.1201\/9781420010749-63"},{"key":"790_CR24","doi-asserted-by":"publisher","unstructured":"Talwar K (2004) Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of 36th ACM symposium on theory of computing (STOC 2004), pp 281\u2013290. https:\/\/doi.org\/10.1145\/1007352.1007399","DOI":"10.1145\/1007352.1007399"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00790-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00790-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00790-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T21:05:17Z","timestamp":1648587917000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00790-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,6]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["790"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00790-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,8,6]]},"assertion":[{"value":"23 July 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 August 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}