# BalLOT: Balanced k-means clustering with optimal transport

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 35 references that are in the map.
- First posted on arXiv 5 Dec 2025.

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

- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Computational Optimal Transport](https://mlsanity.com/paper/1803.00567/) (2018)
- [Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration](https://mlsanity.com/paper/1705.09634/) (2017)
- [Fast Computation of Wasserstein Barycenters](https://mlsanity.com/paper/1310.4375/) (2013)
- [Computational Optimal Transport: Complexity by Accelerated Gradient Descent Is Better Than by Sinkhorn's Algorithm](https://mlsanity.com/paper/1802.04367/) (2018)
- [Statistical and Computational Guarantees of Lloyd's Algorithm and its Variants](https://mlsanity.com/paper/1612.02099/) (2016)
- [On semidefinite relaxations for the block model](https://mlsanity.com/paper/1406.5647/) (2014)
- [Clustering subgaussian mixtures by semidefinite programming](https://mlsanity.com/paper/1602.06612/) (2016)
- [A Survey of Recent Scalability Improvements for Semidefinite Programming with Applications in Machine Learning, Control, and Robotics](https://mlsanity.com/paper/1908.05209/) (2019)
- [Relax, no need to round: integrality of clustering formulations](https://mlsanity.com/paper/1408.4045/) (2014)
- [Probably certifiably correct k-means clustering](https://mlsanity.com/paper/1509.07983/) (2015)
- [When Do Birds of a Feather Flock Together? k-Means, Proximity, and Conic Programming](https://mlsanity.com/paper/1710.06008/) (2017)
- [The ratio-cut polytope and K-means clustering](https://mlsanity.com/paper/2006.15225/) (2020)
- [Recovery guarantees for exemplar-based clustering](https://mlsanity.com/paper/1309.3256/) (2013)
- [Clustering Semi-Random Mixtures of Gaussians](https://mlsanity.com/paper/1711.08841/) (2017)
- [Hidden Integrality and Semi-random Robustness of SDP Relaxation for Sub-Gaussian Mixture Model](https://mlsanity.com/paper/1803.06510/) (2018)
- [K-median: exact recovery in the extended stochastic ball model](https://mlsanity.com/paper/2109.02547/) (2021)
- [60 years of cyclic monotonicity: a survey](https://mlsanity.com/paper/2308.07682/) (2023)
- [Balanced power diagrams for redistricting](https://mlsanity.com/paper/1710.03358/) (2017)

## Abstract (arXiv)

We consider the fundamental problem of balanced k-means clustering. In particular, we introduce an optimal transport approach to alternating minimization called BalLOT, and we show that it delivers a fast and effective solution to this problem. We establish this with several theoretical guarantees and a variety of numerical experiments. On the theory front, we first prove that for generic data, BalLOT produces integral couplings at each step. Next, we perform a landscape analysis to provide theoretical guarantees for both exact and partial recoveries of planted clusters under the stochastic ball model. We also propose initialization schemes that achieve one-step recovery of planted clusters. To conclude, we present numerical experiments that corroborate our theoretical results.