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, 2020 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$ Sep 16, 2020 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, 2020 at 9:12
  • $\begingroup$ @InuyashaYagami Are the constant factor approximaion algorithm for this problem? $\endgroup$
    – ErroR
    Jan 18, 2022 at 1:49
  • $\begingroup$ @Jut The current best approximation guarantee is $6.129$. See here. The first known constant approximation was around 2 decades earlier. $\endgroup$ Jan 18, 2022 at 6:19


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.