2006 · 36 citations · 9 references
ComputingComputer ScienceMathematicsAlgorithmsComputational GeometryApproximation AlgorithmsGeometric ApproximationStreaming Algorithms
We analyze an extremely simple approximation algo-rithm for computing the minimum enclosing ball (or the 1-center) of a set of points in high dimensions. We prove that this algorithm computes a 3/2-factor approx-imation in any dimension using minimum space in just one pass over the data points. 1
9
Approximate clustering via core-sets
Mihai Bâdoiu, Sariel Har-Peled, Piotr Indyk · 2002 · 369 citations
Approximating extent measures of points
Pankaj K. Agarwal, Sariel Har-Peled, Kasturi Varadarajan · Journal of the ACM · 2004 · 360 citations
A subexponential bound for linear programming
J. Matoušek, M. Sharir, Emo Welzl · Algorithmica · 1996 · 306 citations
Mihai Bâdoiu, Kenneth L. Clarkson · 2003 · 151 citations