# Local Search Yields a PTAS for k-Means in Doubling Metrics

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Mar 2016.

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

- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Multi-Swap k-Means++](https://mlsanity.com/paper/2309.16384/) (2023)
- [A Faster k-means++ Algorithm](https://mlsanity.com/paper/2211.15118/) (2022)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [Relax and Merge: A Simple Yet Effective Framework for Solving Fair k-Means and k-sparse Wasserstein Barycenter Problems](https://mlsanity.com/paper/2411.01115/) (2024)
- [CSCO: Connectivity Search of Convolutional Operators](https://mlsanity.com/paper/2404.17152/) (2024)
- [Hierarchical Clustering via Local Search](https://mlsanity.com/paper/2405.15983/) (2024)
- [Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search](https://mlsanity.com/paper/2502.06163/) (2025)
- [The Computational Complexity of Almost Stable Clustering with Penalties](https://mlsanity.com/paper/2510.03143/) (2025)
- [A Sub-4 Approximation for Fair k-Means](https://mlsanity.com/paper/2609.07974/) (2026)

## Abstract (arXiv)

The most well known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly k-means: given a set of data points and a parameter k, select k centres and partition the data points into k clusters around these centres so that the sum of squares of distances of the points to their cluster centre is minimized. Typically these data points lie ℝd for some d≥ 2. k-means and the first algorithms for it were introduced in the 1950's. Since then, hundreds of papers have studied this problem and many algorithms have been proposed for it. The most commonly used algorithm is known as Lloyd-Forgy, which is also referred to as "the" k-means algorithm, and various extensions of it often work very well in practice. However, they may produce solutions whose cost is arbitrarily large compared to the optimum solution. Kanungo et al. [2004] analyzed a simple local search heuristic to get a polynomial-time algorithm with approximation ratio 9+ε for any fixed ε>0 for k-means in Euclidean space. Finding an algorithm with a better approximation guarantee has remained one of the biggest open questions in this area, in particular whether one can get a true PTAS for fixed dimension Euclidean space. We settle this problem by showing that a simple local search algorithm provides a PTAS for k-means in ℝd for any fixed d. More precisely, for any error parameter ε>0, the local search algorithm that considers swaps of up to ρ=dO(d)·ε-O(d/ε) centres at a time finds a solution using exactly k centres whose cost is at most a (1+ε)-factor greater than the optimum. Finally, we provide the first demonstration that local search yields a PTAS for the uncapacitated facility location problem and k-median with non-uniform opening costs in doubling metrics.