# A bi-criteria approximation algorithm for k Means

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Jul 2015.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Explainable k-means. Don't be greedy, plant bigger trees!](https://mlsanity.com/paper/2111.03193/) (2021)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)

## Abstract (arXiv)

We consider the classical k-means clustering problem in the setting bi-criteria approximation, in which an algoithm is allowed to output β k > k clusters, and must produce a clustering with cost at most α times the to the cost of the optimal set of k clusters. We argue that this approach is natural in many settings, for which the exact number of clusters is a priori unknown, or unimportant up to a constant factor. We give new bi-criteria approximation algorithms, based on linear programming and local search, respectively, which attain a guarantee α(β) depending on the number β k of clusters that may be opened. Our gurantee α(β) is always at most 9 + ε and improves rapidly with β (for example: α(2)<2.59, and α(3) < 1.4). Moreover, our algorithms have only polynomial dependence on the dimension of the input data, and so are applicable in high-dimensional settings.