k-center algorithm in one-dimensional space
First,


  There exist optimal solutions in which each cluster consists of a contiguous sequence of points in the real line.


Any other optimal solutions can be transformed into the cases above. In the following, we focus on the optimal solutions of the kind above.



The complexity of the following "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.

The case for $k=1$ is easy. Denote the optimal solution to $k=1$ in $n$ points by $R_{n,1}$.

Let $R(n,k)$ be the optimal solution for the problem of $k$-center in the first $n$ points. For convenience, define $R(n,k) = 0$ if $k \ge n$ (This is reasonable because we can choose each point as the center of the cluster consisting of only itself).

For general $k &gt; 1$, we consider all the cases according to the number (denoted $m$) of points that are assigned to the last cluster (that is, the last cluster contains a contiguous sequence of the rightmost $m$ points).

$$R(n,k) = \min_{0 \le m \le n} \{ R(n-m, k-1) + R_{m,1} \}$$

The complexity of the "dynamic programming" algorithm is $O(n^2 k) = O(n^3)$.



Note: This paper [1] gives an $O(n \log n)$ time algorithm.



[1] Efficient Algorithms for the One-Dimensional $k$-Center Problem. arXiv, 2014.