Stanford InfoLab Publication Server

On the Worst Case Complexity of the k-means Method

Arthur, David and Vassilvitskii, Sergei (2005) On the Worst Case Complexity of the k-means Method. Technical Report. Stanford.




The k-means method is an old but popular clustering algorithm known for its speed and simplicity. Until recently, however, no meaningful theoretical bounds were known on its running time. In this paper, we demonstrate that the worst-case running time of k-means is superpolynomial by improving the best known lower bound from $\Omega(n)$ iterations to $2^{\Omega(\sqrt{n})}$. To complement this lower bound, we show a smoothed-analysis type polynomial time upper bound for k-means.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:k-means, clustering, heuristic analysis, smoothed complexity
Subjects:Computer Science > Data Mining
ID Code:698
Deposited By:Import Account
Deposited On:02 Nov 2005 16:00
Last Modified:22 Dec 2008 17:41

Download statistics

Repository Staff Only: item control page