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.

 BibTeX DublinCore EndNote HTML

 Preview
PDF
353Kb

Abstract

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) k-means, clustering, heuristic analysis, smoothed complexity Computer Science > Data Mining Miscellaneous 698 Import Account 02 Nov 2005 16:00 22 Dec 2008 17:41