{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T14:13:18Z","timestamp":1740147198951,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T00:00:00Z","timestamp":1638489600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T00:00:00Z","timestamp":1638489600000},"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":["Adv Data Anal Classif"],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s11634-021-00481-4","type":"journal-article","created":{"date-parts":[[2021,12,3]],"date-time":"2021-12-03T05:02:42Z","timestamp":1638507762000},"page":"1039-1067","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial approximate discretization of geometric centers in high-dimensional Euclidean space"],"prefix":"10.1007","volume":"16","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,12,3]]},"reference":[{"key":"481_CR1","unstructured":"Agarwal P, Har-Peled S, Varadarajan K (2005) Geometric approximation via coresets. In: Combinatorial and computational geometry. MSRI Publications\u00a052, pp 1\u201330. Cambridge University Press. http:\/\/library.msri.org\/books\/Book52\/files\/01agar.pdf"},{"issue":"4","key":"481_CR2","doi-asserted-by":"publisher","first-page":"FOCS17-97","DOI":"10.1137\/18M1171321","volume":"49","author":"S Ahmadian","year":"2020","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2020) Better guarantees for $$k$$-means and Euclidean $$k$$-median by primal-dual algorithms. SIAM J Comput 49(4):FOCS17-97-FOCS17-156. https:\/\/doi.org\/10.1137\/18M1171321","journal-title":"SIAM J Comput"},{"key":"481_CR3","doi-asserted-by":"publisher","DOI":"10.5555\/578775","volume-title":"The design and analysis of computer algorithms","author":"A Aho","year":"1974","unstructured":"Aho A, Hopcroft J, Ullman J (1974) The design and analysis of computer algorithms. Addison-Wesley, New York. https:\/\/doi.org\/10.5555\/578775"},{"key":"481_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-6666-3","volume-title":"Combinatorial theory","author":"M Aigner","year":"1979","unstructured":"Aigner M (1979) Combinatorial theory. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-1-4615-6666-3"},{"issue":"2","key":"481_CR5","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 (2009) NP-hardness of Euclidean sum-of-squares clustering. Mach Learn 75(2):245\u2013248. https:\/\/doi.org\/10.1007\/s10994-009-5103-0","journal-title":"Mach Learn"},{"key":"481_CR6","unstructured":"Bhattacharya A, Goyal D, Jaiswal R (2020) Hardness of approximation of Euclidean $$k$$-median. arXiv:2011.04221 [cs.CC]"},{"key":"481_CR7","doi-asserted-by":"crossref","unstructured":"B\u01cedoiu M, Har-Peled S, Indyk P (2002) Approximate clustering via core-sets. In: Proceedings 34th ACM symposium on theory of computing (STOC\u00a02002), pp 250\u2013257. https:\/\/doi.org\/10.1145\/509907.509947","DOI":"10.1145\/509907.509947"},{"issue":"3","key":"481_CR8","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen K (2009) On coresets for $$k$$-median and $$k$$-means clustering in metric and Euclidean spaces and their applications. SIAM J Comput 39(3):923\u2013947. https:\/\/doi.org\/10.1137\/070699007","journal-title":"SIAM J Comput"},{"issue":"2","key":"481_CR9","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1287\/ijoc.11.2.138","volume":"11","author":"W Cook","year":"1999","unstructured":"Cook W, Rohe A (1999) Computing minimum-weight perfect matchings. INFORMS J Comput 11(2):138\u2013148. https:\/\/doi.org\/10.1287\/ijoc.11.2.138","journal-title":"INFORMS J Comput"},{"key":"481_CR10","doi-asserted-by":"crossref","unstructured":"Feder T, Greene D (1988) Optimal algorithms for approximate clustering. In: Proceedings of the 20th ACM symposium on theory of computing (STOC\u00a01988), pp 434\u2013444. https:\/\/doi.org\/10.1145\/62212.62255","DOI":"10.1145\/62212.62255"},{"key":"481_CR11","doi-asserted-by":"crossref","unstructured":"Feldman D, Monemizadeh M, Sohler C (2007) A PTAS for $$k$$-means clustering based on weak coresets. In: Proceedings of the 23rd ACM symposium on computational geometry, pp 11\u201318. https:\/\/doi.org\/10.1145\/1247069.1247072","DOI":"10.1145\/1247069.1247072"},{"key":"481_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 (1985) Clustering to minimize the maximum intercluster distance. Theor Comput Sci 38:293\u2013306. https:\/\/doi.org\/10.1016\/0304-3975(85)90224-5","journal-title":"Theor Comput Sci"},{"key":"481_CR13","unstructured":"Guruswami V, Indyk P (2003) Embeddings and non-approximability of geometric problems. In: Proceedings of the 14th ACM-SIAM symposium on discrete algorithms (SODA\u00a02003), pp 537\u2013538. https:\/\/doi.org\/10.5555\/644108.644198"},{"key":"481_CR14","doi-asserted-by":"crossref","unstructured":"Inaba M, Katoh N, Imai H (1994) Applications of weighted Voronoi diagrams and randomization to variance-based $$k$$-clustering (extended abstract). In: Proceedings of the 10th ACM symposium on computational geometry, pp 332\u2013339. https:\/\/doi.org\/10.1145\/177424.178042","DOI":"10.1145\/177424.178042"},{"issue":"1","key":"481_CR15","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"},{"key":"481_CR16","doi-asserted-by":"crossref","unstructured":"Kel\u2019manov A, Pyatkin A (2011) NP-completeness of some problems of choosing a vector subset. J Appl Ind Math 5(3):352\u2013357. https:\/\/doi.org\/10.1134\/S1990478911030069","DOI":"10.1134\/S1990478911030069"},{"key":"481_CR17","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":"481_CR18","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"},{"key":"481_CR19","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ipl.2016.11.009","volume":"120","author":"E Lee","year":"2017","unstructured":"Lee E, Schmidt M, Wright J (2017) Improved and simplified inapproximability for $$k$$-means. Inf Proc Lett 120:40\u201343. https:\/\/doi.org\/10.1016\/j.ipl.2016.11.009","journal-title":"Inf Proc Lett"},{"key":"481_CR20","doi-asserted-by":"crossref","unstructured":"Lyubashevsky V, Prest T (2015) Quadratic time, linear space algorithms for Gram\u2013Schmidt orthogonalization and Gaussian sampling in structured lattices. In: Proceedings of the 34th conference on the theory and applications of cryptographic techniques (EUROCRYPT\u00a02015), LNCS\u00a09056, pp 789\u2013815. https:\/\/doi.org\/10.1007\/978-3-662-46800-5_30","DOI":"10.1007\/978-3-662-46800-5_30"},{"issue":"3","key":"481_CR21","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1016\/S0747-7171(08)80067-3","volume":"10","author":"N Megiddo","year":"1990","unstructured":"Megiddo N (1990) On the complexity of some geometric problems in unbounded dimension. J Symb Comput 10(3):327\u2013334. https:\/\/doi.org\/10.1016\/S0747-7171(08)80067-3","journal-title":"J Symb Comput"},{"issue":"1","key":"481_CR22","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1137\/0213014","volume":"13","author":"N Megiddo","year":"1984","unstructured":"Megiddo N, Supowit K (1984) On the complexity of some common geometric location problems. SIAM J Comput 13(1):182\u2013196. https:\/\/doi.org\/10.1137\/0213014","journal-title":"SIAM J Comput"},{"key":"481_CR23","unstructured":"Mentzer S (1988) Approximability of metric clustering problems. https:\/\/www.academia.edu\/23251714\/Approximability_of_Metric_Clustering_Problems"},{"issue":"3","key":"481_CR24","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 Ind Math 6(3):381\u2013386. https:\/\/doi.org\/10.1134\/S1990478912030131","journal-title":"J Appl Ind Math"},{"key":"481_CR25","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":"481_CR26","doi-asserted-by":"crossref","unstructured":"Shenmaier V (2021) Linear-size universal discretization of geometric center-based problems in fixed dimensions. J Combin Optim. https:\/\/doi.org\/10.1007\/s10878-021-00790-6","DOI":"10.1007\/s10878-021-00790-6"}],"container-title":["Advances in Data Analysis and Classification"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11634-021-00481-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11634-021-00481-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11634-021-00481-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,5]],"date-time":"2022-11-05T10:45:46Z","timestamp":1667645146000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11634-021-00481-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,3]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["481"],"URL":"https:\/\/doi.org\/10.1007\/s11634-021-00481-4","relation":{},"ISSN":["1862-5347","1862-5355"],"issn-type":[{"type":"print","value":"1862-5347"},{"type":"electronic","value":"1862-5355"}],"subject":[],"published":{"date-parts":[[2021,12,3]]},"assertion":[{"value":"16 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 October 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 December 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}