An effective variant of the Hartigan k-means algorithm

François Clément, Stefan Steinerberger
4/23/2026
cs.LG

No confident code implementation found for this paper.

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.

View on arXivView PDF

Code Implementations

No confident code match yet

We couldn't find an author-owned or strongly-evidenced community implementation for this paper. Any repos shown below are weak matches — verify before relying on them.

No code implementations found yet.

Know of an implementation? Let us know in the comments below!

Similar Papers

Improved Outlier Robust Seeding for k-means

88% match2023

Are Easy Data Easy (for K-Means)

86% match2023

MNAR-k-means: A k-means Clustering for Data Missing Not at Random with Magnitude-Decaying Probability

85% match2026

Fixed-sized clusters k-Means

85% match2025

Scalable Clustering: Large Scale Unsupervised Learning of Gaussian Mixture Models with Outliers

84% match2023

K*-Means: A Parameter-free Clustering Algorithm

83% match2025

Cite this paper

@article{clment2026effective,
  title  = {An effective variant of the Hartigan k-means algorithm},
  author = {François Clément and Stefan Steinerberger},
  year   = {2026},
  eprint = {2604.21798},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2604.21798v1}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2604.21798.svg)](https://codeofpaper.com/paper/2604.21798)

Discussion