Abstract
We present the first linear time (1+ε)-approximation algorithm for the k-means problem for fixed k and ε. Our algorithm runs in O(nd) time, which is linear in the size of the input. Another feature of our algorithm is its simplicity – the only technique involved is random sampling. 1.
Keywords
SimplicityAlgorithmSimple (philosophy)Cluster analysisApproximation algorithmTime complexityComputer scienceSimple random sampleSampling (signal processing)SIMPLE algorithmMathematicsFeature (linguistics)Artificial intelligencePhysics
Affiliated Institutions
Related Publications
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...
Unsupervised K-Means Clustering Algorithm
The k-means algorithm is generally the most known and used clustering method. There are various extensions of k-means to be proposed in the literature. Although it is an unsuper...
SLIC Superpixels Compared to State-of-the-Art Superpixel Methods
Computer vision applications have come to rely increasingly on superpixels in recent years, but it is not always clear what constitutes a good superpixel algorithm. In an effort...
Scaling clustering algorithms to large databases
Practical clustering algorithms require multiple data scans to achieve convergence. For large databases, these scans become prohibitively expensive. We present a scalable cluste...
Weighted Graph Cuts without Eigenvectors A Multilevel Approach
A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods....
Publication Info
- Year
- 2004
- Type
- article
- Pages
- 454-462
- Citations
- 241
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
241
OpenAlex
Cite This
Amit Kumar,
Yogish Sabharwal,
Subhankar Sen
(2004).
A Simple Linear Time (1+ ∊) -Approximation Algorithm for k-Means Clustering in Any Dimensions.
, 454-462.
https://doi.org/10.1109/focs.2004.7
Identifiers
- DOI
- 10.1109/focs.2004.7