Since version 3.4.0, the runtime of this dynamic programming algorithm has been greatly reduced after two changes to trim down the search space. These improvements, not discussed in (Wang and Song, 2011), will be described in future publications. While runtime was at least two times faster for all tested examples, the most notable improvement occurred when $k=2$ or $k$ is very large. First, an upper bound for the sum of within cluster square distances is checked to reduce the dynamic programming search space. Second, the unnecessary calculation of $n-1$ elements in the dynamic programming matrix that do not influence the final result has been eliminated. The asymptotic runtime on $n$ points is improved to $O( (k-1) n^2 + n \lg n)$. When $k=2$, it is $O(n\lg n)$, leading to enormous reduction in runtime: assigning one million points into two clusters took half a second, down from about a week, on iMac with a 2.93 GHz Intel Core i7 processor. Overall, the function now runs fast for all tested input, and the improvements are especially pronounced for $k=2$ and large $k$. The space complexity is $O(kn)$.
Richard Bellman (1973) first described a general dynamic programming strategy for solving univariate clustering problems with additive optimality measures. The strategy, however, did not address any specific characteristics of the $k$-means problem and its implied general algorithm will have a time complexity of $O(kn^3)$ and space complexity of $O(kn)$.
Bellman, R. (1973) A note on cluster analysis and dynamic programming. Mathematical Biosciences 18(3), 311--312.
stats::kmeans function that implements various heuristic $k$-means algorithms.