The Hardness of Approximation of Euclidean k-means.
Pranjal AwasthiMoses CharikarRavishankar KrishnaswamyAli Kemal SinopPublished in: CoRR (2015)
Keyphrases
- k means
- clustering algorithm
- phase transition
- sufficient statistics
- learning theory
- hierarchical clustering
- data clustering
- np hard
- euclidean distance
- worst case
- approximation algorithms
- spectral clustering
- cluster analysis
- closed form
- expectation maximization
- unsupervised clustering
- computational complexity
- approximation error
- approximation methods
- data sets
- euclidean space
- rough k means
- relative error
- fuzzy c means
- self organizing maps
- special case
- optimal solution
- bayesian networks
- similarity measure
- data mining
- neural network