Smaller coresets for k-median and k-means clustering

Sariel Har-Peled, Akash Kushal

Research output: Contribution to journalArticlepeer-review


In this paper we show that there exists a (k, ε)-coreset for k-median and k-means clustering of n points in ℜd which is of size independent of n. In particular, we construct a (k, ε)-coreset of size O(k2 / εd) for k-median clustering, and of size O(k3 / εd+1) for k-means clustering.

Original languageEnglish (US)
Pages (from-to)3-19
Number of pages17
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jan 2007

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Smaller coresets for k-median and k-means clustering'. Together they form a unique fingerprint.

Cite this