Approximate clustering via core-sets

Mihai Bǎdoiu, Sariel Har-Peled, Piotr Indyk

Research output: Contribution to journalConference articlepeer-review

Abstract

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.

Original languageEnglish (US)
Pages (from-to)250-257
Number of pages8
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
StatePublished - Jan 1 2002
Externally publishedYes
EventProceedings of the 34th Annual ACM Symposium on Theory of Computing - Montreal, Que., Canada
Duration: May 19 2002May 21 2002

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Approximate clustering via core-sets'. Together they form a unique fingerprint.

Cite this