mlsanityData to 7 Oct 2026

Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms

arXiv 1612.07925 ↗First posted 23 Dec 2016cs.DScited by 54

Not on the map. Why?

Abstract (arXiv)

Clustering is a classic topic in optimization with k-means being one of the most fundamental such problems. In the absence of any restrictions on the input, the best known algorithm for k-means with a provable guarantee is a simple local search heuristic yielding an approximation guarantee of 9+ε, a ratio that is known to be tight with respect to such methods. We overcome this barrier by presenting a new primal-dual approach that allows us to (1) exploit the geometric structure of k-means and (2) to satisfy the hard constraint that at most k clusters are selected without deteriorating the approximation guarantee. Our main result is a 6.357-approximation algorithm with respect to the standard LP relaxation. Our techniques are quite general and we also show improved guarantees for the general version of k-means where the underlying metric is not required to be Euclidean and for k-median in Euclidean metrics.

Key facts. Cited by 54 papers in the map (data through 7 Oct 2026). First posted on arXiv 23 Dec 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 17; 2022: 16; 2023: 8; 2024: 6; 2025: 3; 2026: 4.

54 papers.

Sort:

  1. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  2. 2021Learning-Augmented k-means Clusteringcited by 26
  3. 2022Towards Optimal Lower Bounds for k-median and k-means Coresetscited by 23
  4. 2021Fair Clustering Under a Bounded Costcited by 21
  5. 2021Locally Private k-Means in One Roundcited by 19
  6. 2023Replicable Clusteringcited by 19
  7. 2021Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraintscited by 17
  8. 2021Nearly-Tight and Oblivious Algorithms for Explainable Clusteringcited by 17
  9. 2021Differentially-Private Clustering of Easy Instancescited by 17
  10. 2021Explainable k-means. Don't be greedy, plant bigger trees!cited by 15
  11. 2022Improved Approximations for Euclidean k-means and k-median, via Nested Quasi-Independent Setscited by 14
  12. 2021Near-Optimal Explainable k-Means for All Dimensionscited by 13
38 more
  1. 2021Near-optimal Algorithms for Explainable k-Medians and k-Meanscited by 13
  2. 2021Approximating Fair Clustering with Cascaded Norm Objectivescited by 13
  3. 2021Consistency of Constrained Spectral Clustering under Graph Induced Fair Planted Partitionscited by 10
  4. 2022Scalable Differentially Private Clustering via Hierarchically Separated Treescited by 10
  5. 2022Differentially Private Vertical Federated Clusteringcited by 10
  6. 2022Improved Learning-augmented Algorithms for k-means and k-medians Clusteringcited by 10
  7. 2021Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metricscited by 8
  8. 2022A Nearly Tight Analysis of Greedy k-means++cited by 7
  9. 2023Do you know what q-means?cited by 6
  10. 2023Initializing Services in Interactive ML Systems for Diverse Userscited by 5
  11. 2022k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacycited by 4
  12. 2022The computational complexity of some explainable clustering problemscited by 4
  13. 2022A Faster k-means++ Algorithmcited by 4
  14. 2023Multi-Swap k-Means++cited by 4
  15. 2024Diversity-aware clustering: Computational Complexity and Approximation Algorithmscited by 3
  16. 2021Online k-means Clustering on Arbitrary Data Streamscited by 2
  17. 2021Coresets for constrained k-median and k-means clustering in low dimensional Euclidean spacecited by 2
  18. 2021Differentially-Private Sublinear-Time Clusteringcited by 2
  19. 2022Tackling Provably Hard Representative Selection via Graph Neural Networkscited by 2
  20. 2022A Generative Framework for Personalized Learning and Estimation: Theory, Algorithms, and Privacycited by 2
  21. 2023Parameterized Approximation for Robust Clustering in Discrete Geometric Spacescited by 2
  22. 2023Simple, Scalable and Effective Clustering via One-Dimensional Projectionscited by 2
  23. 2024Optimization of Inter-group Criteria for Clustering with Minimum Size Constraintscited by 2
  24. 2024A Differentially Private Clustering Algorithm for Well-Clustered Graphscited by 2
  25. 2026Delayed Assignments in Online Non-Centroid Clustering with Stochastic Arrivalscited by 2
  26. 2021Differentially Private Algorithms for Clustering with Stability Assumptionscited by 1
  27. 2022Fast Distributed k-Means with a Small Number of Roundscited by 1
  28. 2023Impossibility of Depth Reduction in Explainable Clusteringcited by 1
  29. 2023Differentially Private Clustering in Data Streamscited by 1
  30. 2024The Fairness-Quality Trade-off in Clusteringcited by 1
  31. 2025Label-consistent clustering for evolving datacited by 1
  32. 2022Distributed k-Means with Outliers in General Metricscited by 0
  33. 2022On consistency of constrained spectral clustering under representation-aware stochastic block modelcited by 0
  34. 2022Bicriteria Approximation Algorithms for Priority Matroid Mediancited by 0
  35. 2022Can Evolutionary Clustering Have Theoretical Guarantees?cited by 0
  36. 2024A cutting plane algorithm for globally solving low dimensional k-means clustering problemscited by 0
  37. 2024Faster and Simpler Greedy Algorithm for k-Median and k-Meanscited by 0
  38. 2025Number of Clusters in a Dataset: A Regularized K-means Approachcited by 0

50 most cited of 54 All 54 (JSON)