k-Means has Polynomial Smoothed Complexity

David Arthur Bodo Manthey Heiko Röglin

Published in: CoRR (2009)

Keyphrases

k means
clustering algorithm
polynomial hierarchy
vapnik chervonenkis dimension
decision problems
cluster analysis
spectral clustering
space complexity
database
machine learning
information systems
case study
computational cost
lower complexity
exponential size