How fast can we optimally cluster 1-D data?

Question

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) is minimized overall, i.e. the clusters as as "tight" as possible.

While NP-hard in the general case, I know it is $\text{PTIME}$-tractable if the points are on a line.

What is the best known upper bound on the time complexity of optimal clustering for the 1-dimensional case?

Note: Lower bounds are also interesting, but less so.

Answer 1

Here's what my search has come up with:

There's a straightforward dynamic programming solution of the problem in this case, which requires $\mathop{\Omega}\left( k \cdot n^3 \right)$ time; and with some thought one can avoid redundant computation of sums-of-squares by this algorithm, reducing the complexity to $\mathop{\Omega}\left( k \cdot n^2 \right)$. This is described in:

Wang, Haizhou, and Mingzhou Song. Ckmeans. 1d. dp: optimal k-means clustering in one dimension by dynamic programming. The R journal 3, no. 2 (2011): 29.

That being said - I'm thinking perhaps this can be improved to $\mathop{o} \left( k \cdot n \log{n} \right)$ somehow, or at least $\mathop{\omega} \left( k \cdot n^2 \right)$.