# Differentially Private Clustering: Tight Approximation Ratios

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Aug 2020.

## Built on by (most cited first, 30 of 34)

- [Differentially Private Synthetic Data via Foundation Model APIs 1: Images](https://mlsanity.com/paper/2305.15560/) (2023)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Replicable Clustering](https://mlsanity.com/paper/2302.10359/) (2023)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Vertical Federated Clustering](https://mlsanity.com/paper/2208.01700/) (2022)
- [Data-adaptive Differentially Private Prompt Synthesis for In-Context Learning](https://mlsanity.com/paper/2410.12085/) (2024)
- [Smooth Lower Bounds for Differentially Private Algorithms via Padding-and-Permuting Fingerprinting Codes](https://mlsanity.com/paper/2307.07604/) (2023)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Urania: Differentially Private Insights into AI Use](https://mlsanity.com/paper/2506.04681/) (2025)
- [Differentially Private Nonparametric Regression Under a Growth Condition](https://mlsanity.com/paper/2111.12786/) (2021)
- [Private Learning of Littlestone Classes, Revisited](https://mlsanity.com/paper/2510.00076/) (2025)
- [Differentially-Private Sublinear-Time Clustering](https://mlsanity.com/paper/2112.13751/) (2021)
- [A Generative Framework for Personalized Learning and Estimation: Theory, Algorithms, and Privacy](https://mlsanity.com/paper/2207.01771/) (2022)
- [Differential Privacy for Clustering Under Continual Observation](https://mlsanity.com/paper/2307.03430/) (2023)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [FastLloyd: Federated, Accurate, Secure, and Tunable k-Means Clustering with Differential Privacy](https://mlsanity.com/paper/2405.02437/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [Differentially Private Multi-Sampling from Distributions](https://mlsanity.com/paper/2412.10512/) (2024)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Differentially Private Partial Set Cover with Applications to Facility Location](https://mlsanity.com/paper/2207.10240/) (2022)
- [DPM: Clustering Sensitive Data through Separation](https://mlsanity.com/paper/2307.02969/) (2023)
- [Differentially Private Clustering in Data Streams](https://mlsanity.com/paper/2307.07449/) (2023)
- [Towards the mathematical foundation of the minimum enclosing ball and related problems](https://mlsanity.com/paper/2402.06629/) (2024)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)
- [Making Old Things New: A Unified Algorithm for Differentially Private Clustering](https://mlsanity.com/paper/2406.11649/) (2024)
- [Personalized Privacy Amplification via Importance Sampling](https://mlsanity.com/paper/2307.10187/) (2023)

## Abstract (arXiv)

We study the task of differentially private clustering. For several basic clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and k-median, we give efficient differentially private algorithms that achieve essentially the same approximation ratios as those that can be obtained by any non-private algorithm, while incurring only small additive errors. This improves upon existing efficient algorithms that only achieve some large constant approximation factors. Our results also imply an improved algorithm for the Sample and Aggregate privacy framework. Furthermore, we show that one of the tools used in our 1-Cluster algorithm can be employed to get a faster quantum algorithm for ClosestPair in a moderate number of dimensions.