Exact algorithms for $k$-means

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.

• Thanks, I've elaborated more on it. – Andrea Sep 15 at 21:50
• @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. – Inuyasha yagami Sep 16 at 6:22
• 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. – Yonatan N Sep 16 at 9:12