Approximate Clustering via Core-Sets

Mihai Badoiu, Sariel Har-Peled, and Piotr Indyk.

In this paper, we show that for several clustering problems one can extract a small set of points, so that using those \em core-sets enable us to perform approximate clustering efficiently. The surprising property of those core-sets is that their size is independent of the dimension.

Using those, we present a (1+µ)-approximation algorithms for the k-center clustering and k-median clustering problems in Euclidean space. The running time of the new algorithms has linear or near linear dependency on the number of points and the dimension, and exponential dependency on 1/µ and k. As such, our results are a substantial improvement over what was previously known.

We also present some other clustering results including (1+µ)-approximate 1-cylinder clustering, and k-center clustering with outliers.

Postscript, PDF.

Last updated: Tue Feb 19 18:56:28 CST 2002