5
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • 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$
    – Inuyasha Yagami
    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$
    – MR_
    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$
    – Inuyasha Yagami
    Jan 18, 2022 at 6:19

0

Reset to default

Your Answer

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