\hfill \\
\end{gathered} \right)} i^N$$ which can be approximated by $K^N/K!$ It can be seen that a complete enumeration of all possible clusterings to determine the global minimum of is clearly computationally prohibitive except for very small data sets [@Kaufman90]. In fact, this non-convex optimization problem is proven to be NP-hard even for $K = 2$ [@Aloise09] or $D = 2$ [@Mahajan12]. Consequently, various heuristics have been developed to provide approximate solutions to this problem [@Tarsitano03]. Among these heuristics, Lloyd’s algorithm [@Lloyd82], often referred to as the (batch) k-means algorithm, is the simplest and most commonly used one. This algorithm starts with $K$ arbitrary centers, typically chosen uniformly at random from the data points. Each point is assigned to the nearest center and then each center is recalculated as the mean of all points assigned to it. These two steps are repeated until a predefined termination criterion is met.

The k-means algorithm is undoubtedly the most widely used partitional clustering algorithm [@Jain10]. Its popularity can be attributed to several reasons. First, it is conceptually simple and easy to implement. Virtually every data mining software includes an implementation of it. Second, it is versatile, i.e., almost every aspect of the algorithm 