k-means Requires Exponentially Many Iterations Even in the Plane

By Andrea Vattani. SCG '09, 2008

307 citations recorded by the source corpus.

The k-means algorithm is a well-known method for partitioning n points that lie in the d-dimensional space into k clusters. Its main features are simplicity and speed in practice. Theoretically, however, the best known upper bound on its running time (i.e., nO(kd)) is, in general, exponential in the number of points (when kd=Ω(n/log n)). Recently Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006) showed a super-polynomial worst-case analysis, improving the best known lower bound from Ω(n) to $2^{\varOmega (\sqrt{n})}$ with a construction in $d=\varOmega (\sqrt{n})$ dimensions. In Arthur and Vassilvitskii (Proceedings of the 22nd Annual Symposium on Computational Geometry, pp. 144–153, 2006), they also conjectured the existence of super-polynomial lower bounds for any d≥2.Our contribution is twofold: we prove this conjecture and we improve the lower bound, by presenting a simple construction in the plane that leads to the exponential lower bound 2Ω(n).

Subfields: Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/55b8c0b9309840b3b0dc6bd694060b247f15d3b6

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Computer Vision and Pattern Recognition

Citations in the corpus

Data stream clustering: A survey (2013, background): “There are theoretical papers that provide the upper bound on its running time [Vattani 2009; Arthur and Vassilvitskii 2006], which can be exponential even for low-dimensional data.”
Scalable K-Means++ (2012, background): “…standpoint, k -means is not a good clustering algorithm in terms of eﬃciency or quality: the running time can be exponential in the worst case [32, 4] and even though the ﬁnal solution is locally optimal, it can be very far away from the global optimum (even under repeated random…”