Complexity of minimizing the maximum inter-cluster distance?

Question

Given $n$ non overlapping points $x_i \in \mathbb{Q}$, and an integer $k\geq 2$, what is known about the complexity of finding $k$ means ($a_1, a_2, ..., a_k$) that minimize the maximum inter cluster distance: $$\min_{a_1, ..., a_k \in \mathbb{Q}}\max_{1\leq j \leq k} \sum_{x_i \in C_j}||x_i-a_j||^2$$

Do we have any polynomial time algorithms for general $k$?, specific $k$ (say $k=2$)? Does the problem have a special name?

Answer 1

Because you are working in one dimension, there's a polynomial-time algorithm, using dynamic programming. Assume $x_1,\dots,x_n$ are sorted in increasing order. Notice that each cluster must contain a contiguous sequence of $x$'s, say $x_i,x_{i+1},\dots,x_j$. Let $f(n_0,k_0)$ denote the minimum of the maximum inter cluster distance for dividing the points $x_1,\dots,x_{n_0}$ into $k_0$ clusters. Then you can express $f(n_0,k_0)$ in terms of $f(m,k_0-1)$ for $m<n_0$:

$$f(n_0,k_0) = \min_m \max(f(m,k_0-1), \text{variance}(x_{m+1},x_{m+2},\dots,x_{n_0})),$$

where $m$ ranges over $m=1,2,\dots,n_0-1$.

Consequently, you can evaluate $f(\cdot,\cdot)$ at all $O(nk)$ inputs in $O(n^2k)$ time. You can improve this to $O(nk)$ time by setting $g(n_0,k_0)=\min(f(1,k_0),\dots,f(n_0,k_0))$ and noting

$$\begin{align*} f(n_0,k_0) &= \max(g(m,k_0-1), \text{variance}(x_{m+1},x_{m+2},\dots,x_{n_0}))\\ g(n_0,k_0) &= \min(g(n_0,k_0-1), f(n_0,k_0)). \end{align*}$$

You will need to use the fact that you can compute the mean and variance of $x_{m+1},\dots,x_{n_0}$ from the mean and variance of $x_1,\dots,x_m$ and the mean and variance of $x_1,\dots,x_{n_0}$. You can compute the mean and variance of $x_1,\dots,x_{n_0}$ for all $n_0$ in $O(n)$ time by maintaining a running sum and running sum of squares.

Answer 2

Based on Wikipedia documentation (here), finding the optimal solution to the k-means clustering problem for observations in d dimensions is:

• NP-hard in general Euclidean space (of d dimensions) even for two clusters
• NP-hard for a general number of clusters k even in the plane
• if $k$ and $d$ (the dimension) are fixed, the problem can be exactly solved in time $O(n^{dk+1})$, where $n$ is the number of entities to be clustered

Thus, a variety of heuristic algorithms such as Lloyd's algorithm given above are generally used. The running time of Lloyd's algorithm (and most variants) is $O(nkdi)$ where:

• $n$ is the number of $d$-dimensional vectors (to be clustered)
• $k$ is the number of clusters
• $i$ is the number of iterations needed until convergence.

On data that does have a clustering structure, the number of iterations until convergence is often small, and results only improve slightly after the first dozen iterations. Lloyd's algorithm is therefore often considered to be of "linear" complexity in practice, although it is in the worst case superpolynomial when performed until convergence.