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?


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.

  • $\begingroup$ Thanks @D.W., Interesting, its very similar to the 1D dp for kmeans. Do you happen to know if this is the optimal in literature (anything closer to $O(kn)$?) $\endgroup$ – AspiringMat Dec 11 '19 at 2:04
  • $\begingroup$ @AspiringMat, see updated answer. $\endgroup$ – D.W. Dec 11 '19 at 2:05
  • $\begingroup$ Thanks, really cool speedup. $\endgroup$ – AspiringMat Dec 11 '19 at 2:09

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.

  • $\begingroup$ I think you might've misread my question. This is not the k means problem. k-means minimizes the sum of square distances of inter cluster distances. My problem is minimizing the maximum inter-cluster distance. $\endgroup$ – AspiringMat Dec 11 '19 at 1:54
  • $\begingroup$ Also, k-means can be solved for $d=1$ in time $O(kn^2)$ using a simple dynamic programming algorithm. $\endgroup$ – AspiringMat Dec 11 '19 at 2:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.