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.