Lets recall the definition of $k$-means clustering for euclidean spaces.

Let $X$ be a set of $n$ points in $R^d$ and $k$ a given natural number. Let $C$ any $k$ clustering of $X$. Define the cost of $C$

$\phi(C) = \sum_{i=1}^k \sum_{x \in C_i} \|x-\mu_i\|_2^2$

where $\mu_i = mean(C_i)$.

Then the goal is to find a $C^*$ minimizing $\phi$. This problem is NP-Hard, even for $k=2$.

However there several approximation algorithms for it, e.g. k-means++; but also constant factor approximation algorithms and PTAS.

What I'm looking for is a reference for exact algorithms (i.e., algorithms finding an optimal clustering) which are not polynomial but better than exhastive search. The only reference I'm aware of is (https://dl.acm.org/doi/10.1145/177424.178042), which is quite old.

  • 2
    $\begingroup$ Thanks, I've elaborated more on it. $\endgroup$ – Andrea Sep 15 at 21:50
  • 1
    $\begingroup$ @D.W. Technically, k-means is a problem, as defined in the question. It is just that "Lloyd's heuristic" is popularly known as the k-means algorithm. $\endgroup$ – Inuyasha yagami Sep 16 at 6:22
  • 1
    $\begingroup$ I don't know of recent work on absolute worst-case instances, but k-means on smoothed instances can be solved in polynomial time, see AMR09. $\endgroup$ – Yonatan N Sep 16 at 9:12

Your Answer

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

Browse other questions tagged or ask your own question.