Keywords
Center (category theory)Theory of computationAlgorithmApproximation algorithmCombinatoricsMathematicsCluster analysisk-means clusteringRunning timeSimple (philosophy)Discrete mathematics
Affiliated Institutions
Related Publications
On coresets for k-means and k-median clustering
In this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. In other words, we show that gi...
A local search approximation algorithm for k-means clustering
In k-means clustering we are given a set of n data points in d-dimensional space ℜd and an integer k, and the problem is to determine a set of k points in ℜd, called centers, to...
Approximation schemes for clustering problems
Let k be a fixed integer. We consider the problem of partitioning an input set of points endowed with a distance function into k clusters. We give polynomial time approximation ...
How slow is the <i>k</i> -means method?
The k-means method is an old but popular clustering algorithm known for its observed speed and its simplicity. Until recently, however, no meaningful theoretical bounds were kno...
How fast is the k-means method?
We present polynomial upper and lower bounds on the number of iterations performed by the k-means method (a.k.a. Lloyd's method) for k-means clustering. Our upper bounds are pol...
Publication Info
- Year
- 2002
- Type
- article
- Volume
- 33
- Issue
- 2
- Pages
- 201-226
- Citations
- 244
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
244
OpenAlex
Cite This
Pankaj K. Agarwal,
Cecilia M. Procopiuc
(2002).
Exact and Approximation Algorithms for Clustering.
Algorithmica
, 33
(2)
, 201-226.
https://doi.org/10.1007/s00453-001-0110-y
Identifiers
- DOI
- 10.1007/s00453-001-0110-y