An effective variant of the Hartigan $k$-means algorithm

ArXi:2604.21798v1 Announce Type: new The k-means problem is perhaps the classical clustering problem and often synonymous with Lloyd's algorithm. It has become clear that Hartigan's algorithm gives better results in almost all cases, Telgarsky-Vattani note a typical improvement of $5\%$ -- $10\%$. We point out that a very minor variation of Hartigan's method leads to another $2\%$ -- $5\%$ improvement; the improvement tends to become larger when either dimension or $k$ increase.