# k-center algorithm in one-dimensional space

I'm aware of the general k-center approximation algorithm, but my professor (this is a question from a CS class) says that in a one-dimensional space, the problem can be solved (optimal solution found, not an approximation) in O(n^2) polynomial time without depending on k or using dynamic programming.

A general description of the k-center problem: Given a set of nodes in an n-dimensional space, cluster them into k clusters such that the "radius" of each cluster (distance from furthest node to its center node) is minimized. A more formal and detailed description can be found at http://en.wikipedia.org/wiki/Metric_k-center

As you might expect, I can't figure out how this is possible. The part currently causing me problems is how the runtime can not rely on k.

The nature of the problem causes me to try to step through the nodes on a sort of number line and try to find points to put boundaries, marking off the edges of each cluster that way. But this would require a runtime based on k.

The O(n^2) runtime though makes me think it might involve filling out an nxn array with the distance between two nodes in each entry.

Any explanation on how this is works or tips on how to figure it out would be very helpful.

• The running time need not depend on $k$ since we can assume without loss of generality that $k \leq n$ (why?). Also, the actual running time could depend on $k$, say $O(nk)$, and still be $O(n^2)$. – Yuval Filmus Oct 23 '14 at 14:49
• I see what you're saying, that makes sense. So would what I was thinking earlier be reasonable/on the right track? Step through all the nodes k times and calculate the objective function each step. But at this point it sounds like it'll be a dynamic programming algorithm (which isn't necessary) – philv Oct 23 '14 at 15:48
• I haven't thought about the algorithm, you'll have to figure it out yourself. – Yuval Filmus Oct 23 '14 at 15:48
• If the points and centers are in sorted order, then one can run a k-medians step in linear time. Perhaps it's possible to prove in 1D (1) that there is no local optimum that is not global optimum and (2) that n steps will suffice for convergence. – David Eisenstat Oct 23 '14 at 16:00
• That's helpful, but I think you should make the problem more precise. Do the centers (the warehouses) have to be one of the $n$ original points, or can they be located anywhere on the 1-D line? – D.W. Oct 24 '14 at 4:59

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 > 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.

Hint: In algorithms, if you're not sure how to solve the problem, sometimes it is helpful to look at a scaled down version of the problem. I suggest you start by looking at the version of the problem where $k=1$. I suspect you'll find that the problem is super-easy, when $k=1$ and you are on the 1-D line.

Next, see if you can solve it for $k=2$. I think you'll find that case is pretty easy, too, using the ideas you got from the $k=1$ case.

The obvious next step is to generalize to arbitrary $k$.

Take a look at Jenks natural breaks which are designed to partition a 1D scalar space. You can found a scala implementation of it here.