The most common heuristic to find \(k\) -means clusters is Lloyd's Algorithm [1]}.
It begins with an initial clustering and iteratively computes cluster centroids and assigns points to clusters corresponding to their closest
centroids.
However, using this heuristic with our proposed cost may not guarantee convergence.
(See our discussion after Theorem REF ).
Instead, we adopt an approach based on Hartigan's method [2]}.
For \(k\) -means clustering, Hartigan's method proceeds point by point in a greedy manner. Each point is reassigned to a cluster such that the overall cost is reduced.
