The Hardness of Approximation of Euclidean k-Means.
Pranjal AwasthiMoses CharikarRavishankar KrishnaswamyAli Kemal SinopPublished in: SoCG (2015)
Keyphrases
- k means
- approximation algorithms
- closed form
- approximation error
- phase transition
- euclidean space
- clustering method
- np hard
- spectral clustering
- error bounds
- clustering algorithm
- hierarchical clustering
- data clustering
- data sets
- euclidean distance
- worst case
- computational complexity
- search algorithm
- image segmentation
- error tolerance
- sufficient statistics