Linear-size universal discretization of geometric center-based problems in fixed dimensions

• Agarwal P, Procopiuc C (2002) Exact and approximation algorithms for clustering. Algorithmica 33(2):201–226. https://doi.org/10.1007/s00453-001-0110-y

  Article  MathSciNet  MATH  Google Scholar 

• 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–30. http://library.msri.org/books/Book52/files/01agar.pdf

• Aggarwal A, Imai H, Katoh N, Suri S (1991) Finding \(k\) points with minimum diameter and related problems. J Algorithms 12(1):38–56. https://doi.org/10.1016/0196-6774(91)90022-Q

  Article  MathSciNet  MATH  Google Scholar 

• Alon N, Lee T, Shraibman A, Vempala S (2013a) The approximate rank of a matrix and its algorithmic applications. Extended version of the STOC 2013 paper. https://www.cc.gatech.edu/~vempala/papers/epsrank.pdf

• 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–684. https://doi.org/10.1145/2488608.2488694

• 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–113. https://doi.org/10.1145/276698.276718

• Bǎdoiu 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–257. https://doi.org/10.1145/509907.509947

• 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–90. https://doi.org/10.1145/200836.200853

  Article  MathSciNet  MATH  Google Scholar 

• Chen K (2006) On \(k\)-median clustering in high dimensions. In: Proceedings of 17th ACM-SIAM symposium on discrete algorithms (SODA 2006), pp 1177–1185. https://doi.org/10.5555/1109557.1109687

• Eppstein D, Erickson J (1994) Iterated nearest neighbors and finding minimal polytopes. Disc Comput Geom 11(3):321–350. https://doi.org/10.1007/BF02574012

  Article  MathSciNet  MATH  Google Scholar 

• Har-Peled S, Mendel M (2006) Fast construction of nets in low-dimensional metrics and their applications. SIAM J Comput 35(5):1148–1184. https://doi.org/10.1137/S0097539704446281

  Article  MathSciNet  MATH  Google Scholar 

• 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–300. https://doi.org/10.1145/1007352.1007400

• 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–46. https://doi.org/10.1007/s00453-013-9833-9

  Article  MathSciNet  MATH  Google Scholar 

• 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–145. https://doi.org/10.1134/S0081543818090146

  Article  MathSciNet  Google Scholar 

• Kumar P, Mitchell J, Yıldırım E (2003) Approximate minimum enclosing balls in high dimensions using core-sets. J Exp Algorithmics 8:1–29. https://doi.org/10.1145/996546.996548

  Article  MathSciNet  MATH  Google Scholar 

• Kumar A, Sabharwal Y, Sen S (2010) Linear-time approximation schemes for clustering problems in any dimensions. J ACM 57(2):1–32. https://doi.org/10.1145/1667053.1667054

  Article  MathSciNet  MATH  Google Scholar 

• Matoušek J (2000) On approximate geometric \(k\)-clustering. Discrete Comput Geom 24(1):61–84. https://doi.org/10.1007/s004540010019

  Article  MathSciNet  MATH  Google Scholar 

• Meira A, Miyazawa F, Pedrosa L (2017) Clustering through continuous facility location problems. Theor Comput Sci 657(B):137–145. https://doi.org/10.1016/j.tcs.2016.10.001

  Article  MathSciNet  MATH  Google Scholar 

• 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–295. https://doi.org/10.1007/978-3-030-37599-7_24

• 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–101. https://doi.org/10.1007/978-3-030-58657-7_10

• Shenmaier V (2012) An approximation scheme for a problem of search for a vector subset. J Appl Industr Math 6(3):381–386. https://doi.org/10.1134/S1990478912030131

  Article  MathSciNet  MATH  Google Scholar 

• Shenmaier V (2015) Complexity and approximation of the smallest \(k\)-enclosing ball problem. Eur J Comb 48:81–87. https://doi.org/10.1016/j.ejc.2015.02.011

  Article  MathSciNet  MATH  Google Scholar 

• 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–53.12. https://doi.org/10.1201/9781420010749-63

  Chapter  Google Scholar 

• 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–290. https://doi.org/10.1145/1007352.1007399

Download references