An effective variant of the Hartigan k-means algorithm

arXiv:2604.21798v1 Announce Type: new Abstract: The k-means problem is perhaps the classical clustering problem and often synonymous with Lloyd's algorithm (1957). It has become clear that Hartigan's algorithm (1975) 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.

Related

• Distributionally Robust K-Means Clustering
• A proposal for PU classification under Non-SCAR using clustering and logistic model
• Scalable Model-Based Clustering with Sequential Monte Carlo
• Bounded Graph Clustering with Graph Neural Networks

Source: arXiv cs.LG | 2026-04-24