mlsanityData to 7 Oct 2026

Near-Linear Time Approximation Schemes for Clustering in Doubling Metrics

arXiv 1812.08664 ↗First posted 20 Dec 2018cs.DS cs.CGcited by 14

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 3; 2022: 6; 2023: 3; 2024: 1; 2025: 0; 2026: 1.

14 papers.

Sort:

  1. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  2. 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
  3. 2021Almost Tight Approximation Algorithms for Explainable Clusteringcited by 12
  4. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  5. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  6. 2021Randomized Dimensionality Reduction for Facility Location and Single-Linkage Clusteringcited by 6
  7. 2023Near-Optimal Quantum Coreset Construction Algorithms for Clusteringcited by 6
  8. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  9. 2022Coresets for Relational Data and The Applicationscited by 1
  10. 2023Impossibility of Depth Reduction in Explainable Clusteringcited by 1
  11. 2022k-Center Clustering with Outliers in Sliding Windowscited by 0
  12. 2022Distributed k-Means with Outliers in General Metricscited by 0
2 more
  1. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  2. 2026Sample-and-Search: An Effective Algorithm for Learning-Augmented k-Median Clustering in High dimensionscited by 0