Smaller coresets for k-median and k-means clustering

Sariel Har-Peled, Akash Kushal

Research output: Contribution to conferencePaperpeer-review

Abstract

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(k2d) for k-median clustering, and of size O(k3/εd+1) for k-means clustering.

Original languageEnglish (US)
Pages126-134
Number of pages9
DOIs
StatePublished - 2005
Event21st Annual Symposium on Computational Geometry, SCG'05 - Pisa, Italy
Duration: Jun 6 2005Jun 8 2005

Other

Other21st Annual Symposium on Computational Geometry, SCG'05
Country/TerritoryItaly
CityPisa
Period6/6/056/8/05

Keywords

  • Clustering
  • Coresets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint

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

Cite this