# An effective variant of the Hartigan k-means algorithm

arXiv: https://arxiv.org/abs/2604.21798 · HTML: https://mlsanity.com/paper/2604.21798/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 21 references that are in the map.
- First posted on arXiv 23 Apr 2026.

## Builds on (most cited first, 1 of 1)

- [The Catastrophic Failure of The k-Means Algorithm in High Dimensions, and How Hartigan's Algorithm Avoids It](https://mlsanity.com/paper/2602.09936/) (2026)

## Abstract (arXiv)

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.