Smaller coresets for k-median and k-means clustering

Sariel Har-Peled; Akash Kushal

doi:10.1007/s00454-006-1271-x

Smaller coresets for k-median and k-means clustering

Sariel Har-Peled
, Akash Kushal

Siebel School of Computing and Data Science

Research output: Contribution to journal › Article › peer-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(k² / ε^d) for k-median clustering, and of size O(k³ / ε^d+1) for k-means clustering.

Original language	English (US)
Pages (from-to)	3-19
Number of pages	17
Journal	Discrete and Computational Geometry
Volume	37
Issue number	1
DOIs	https://doi.org/10.1007/s00454-006-1271-x
State	Published - Jan 2007

ASJC Scopus subject areas

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

Online availability

10.1007/s00454-006-1271-x

Library availability

Discover UIUC Full Text

Cite this

@article{a49d6dec1cda4abdb1f669cd87a3e284,

title = "Smaller coresets for k-median and k-means clustering",

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

author = "Sariel Har-Peled and Akash Kushal",

year = "2007",

month = jan,

doi = "10.1007/s00454-006-1271-x",

language = "English (US)",

volume = "37",

pages = "3--19",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "1",

}

TY - JOUR

T1 - Smaller coresets for k-median and k-means clustering

AU - Har-Peled, Sariel

AU - Kushal, Akash

PY - 2007/1

Y1 - 2007/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/33846811413

UR - https://www.scopus.com/pages/publications/33846811413#tab=citedBy

U2 - 10.1007/s00454-006-1271-x

DO - 10.1007/s00454-006-1271-x

M3 - Article

AN - SCOPUS:33846811413

SN - 0179-5376

VL - 37

SP - 3

EP - 19

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

IS - 1

ER -

Smaller coresets for k-median and k-means clustering

Abstract

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this