# Differentially Private Clustering via Maximum Coverage

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

## Key facts

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

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

- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [k-Median Clustering via Metric Embedding: Towards Better Initialization with Differential Privacy](https://mlsanity.com/paper/2206.12895/) (2022)
- [Differentially Private Wasserstein Barycenters](https://mlsanity.com/paper/2510.03021/) (2025)
- [Locally Private k-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error](https://mlsanity.com/paper/2105.15007/) (2021)
- [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)
- [On the Optimal Number of Grids for Differentially Private Non-Interactive K-Means Clustering](https://mlsanity.com/paper/2603.26963/) (2026)
- [PE-means: Improved Differentially Private k-means Clustering through Private Evolution](https://mlsanity.com/paper/2606.00342/) (2026)

## Abstract (arXiv)

This paper studies the problem of clustering in metric spaces while preserving the privacy of individual data. Specifically, we examine differentially private variants of the k-medians and Euclidean k-means problems. We present polynomial algorithms with constant multiplicative error and lower additive error than the previous state-of-the-art for each problem. Additionally, our algorithms use a clustering algorithm without differential privacy as a black-box. This allows practitioners to control the trade-off between runtime and approximation factor by choosing a suitable clustering algorithm to use.