# Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2018.

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

- [Towards Optimal Lower Bounds for k-median and k-means Coresets](https://mlsanity.com/paper/2202.12793/) (2022)
- [Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Sets](https://mlsanity.com/paper/2204.04828/) (2022)
- [Almost Tight Approximation Algorithms for Explainable Clustering](https://mlsanity.com/paper/2107.00774/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clustering](https://mlsanity.com/paper/2107.01804/) (2021)
- [Near-Optimal Quantum Coreset Construction Algorithms for Clustering](https://mlsanity.com/paper/2306.02826/) (2023)
- [Simple, Scalable and Effective Clustering via One-Dimensional Projections](https://mlsanity.com/paper/2310.16752/) (2023)
- [Coresets for Relational Data and The Applications](https://mlsanity.com/paper/2210.04249/) (2022)
- [Impossibility of Depth Reduction in Explainable Clustering](https://mlsanity.com/paper/2305.02850/) (2023)
- [k-Center Clustering with Outliers in Sliding Windows](https://mlsanity.com/paper/2201.02448/) (2022)
- [Distributed k-Means with Outliers in General Metrics](https://mlsanity.com/paper/2202.08173/) (2022)
- [Faster and Simpler Greedy Algorithm for k-Median and k-Means](https://mlsanity.com/paper/2407.11217/) (2024)
- [Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensions](https://mlsanity.com/paper/2603.10721/) (2026)

## Abstract (arXiv)

We consider the classic Facility Location, k-Median, and k-Means problems in metric spaces of doubling dimension d. We give nearly linear-time approximation schemes for each problem. The complexity of our algorithms is 2^(log(1/eps)/eps)O(d2) n log4 n + 2O(d) n log9 n, making a significant improvement over the state-of-the-art algorithms which run in time n^(d/eps)O(d). Moreover, we show how to extend the techniques used to get the first efficient approximation schemes for the problems of prize-collecting k-Medians and k-Means, and efficient bicriteria approximation schemes for k-Medians with outliers, k-Means with outliers and k-Center.