k-Means Has Polynomial Smoothed Complexity.
David ArthurBodo MantheyHeiko RöglinPublished in: FOCS (2009)
Keyphrases
- k means
- vapnik chervonenkis dimension
- clustering algorithm
- polynomial hierarchy
- website
- computational complexity
- worst case
- clustering method
- randomized approximation
- real time
- average case complexity
- exponential size
- unsupervised clustering
- spectral clustering
- decision problems
- data sets
- cluster analysis
- computational cost
- lower bound