In this paper, we show that for several clustering problems one can extract a small set of points, so that using those 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.
|Number of pages
|Conference Proceedings of the Annual ACM Symposium on Theory of Computing
|Published - 2002
|Proceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002 → May 21 2002
ASJC Scopus subject areas