# Fast Exact k-Means, k-Medians and Bregman Divergence Clustering in 1D

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jan 2017.

## Built on by (most cited first, 15 of 15)

- [DRIVE: One-bit Distributed Mean Estimation](https://mlsanity.com/paper/2105.08339/) (2021)
- [GuidedQuant: Large Language Model Quantization via Exploiting End Loss Guidance](https://mlsanity.com/paper/2505.07004/) (2025)
- [MRI Scan Synthesis Methods based on Clustering and Pix2Pix](https://mlsanity.com/paper/2312.05176/) (2023)
- [Dynamic programming by polymorphic semiring algebraic shortcut fusion](https://mlsanity.com/paper/2107.01752/) (2021)
- [Log-Time K-Means Clustering for 1D Data: Novel Approaches with Proof and Implementation](https://mlsanity.com/paper/2412.15295/) (2024)
- [Modified K-means Algorithm with Local Optimality Guarantees](https://mlsanity.com/paper/2506.06990/) (2025)
- [Features for the 0-1 knapsack problem based on inclusionwise maximal solutions](https://mlsanity.com/paper/2211.09665/) (2022)
- [PASCAL: Precise and Efficient ANN- SNN Conversion using Spike Accumulation and Adaptive Layerwise Activation](https://mlsanity.com/paper/2505.01730/) (2025)
- [Mobile Fitting Room: On-device Virtual Try-on via Diffusion Models](https://mlsanity.com/paper/2402.01877/) (2024)
- [Distributed and Rate-Adaptive Feature Compression](https://mlsanity.com/paper/2404.02179/) (2024)
- [Quantization Design for Deep Learning-Based CSI Feedback](https://mlsanity.com/paper/2503.08125/) (2025)
- [SineLoRADelta: Sine-Activated Delta Compression](https://mlsanity.com/paper/2505.21895/) (2025)
- [Metric Hedonic Games on the Line](https://mlsanity.com/paper/2602.05888/) (2026)
- [Inner Product Aware Quantization: Provably Fast, Accurate, and Adaptive Algorithms](https://mlsanity.com/paper/2606.00289/) (2026)
- [Scaffold-Constrained Subset Dynamic Programming for Exact SSE Clustering](https://mlsanity.com/paper/2609.30477/) (2026)

## Abstract (arXiv)

The k-Means clustering problem on n points is NP-Hard for any dimension d≥ 2, however, for the 1D case there exists exact polynomial time algorithms. Previous literature reported an O(kn2) time dynamic programming algorithm that uses O(kn) space. It turns out that the problem has been considered under a different name more than twenty years ago. We present all the existing work that had been overlooked and compare the various solutions theoretically. Moreover, we show how to reduce the space usage for some of them, as well as generalize them to data structures that can quickly report an optimal k-Means clustering for any k. Finally we also generalize all the algorithms to work for the absolute distance and to work for any Bregman Divergence. We complement our theoretical contributions by experiments that compare the practical performance of the various algorithms.