Differentially Private Clustering: Tight Approximation Ratios

Abstract

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Ghazi et al. "Differentially Private Clustering: Tight Approximation Ratios." Neural Information Processing Systems, 2020.

Markdown

[Ghazi et al. "Differentially Private Clustering: Tight Approximation Ratios." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/ghazi2020neurips-differentially/)

BibTeX

@inproceedings{ghazi2020neurips-differentially,
  title     = {{Differentially Private Clustering: Tight Approximation Ratios}},
  author    = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin},
  booktitle = {Neural Information Processing Systems},
  year      = {2020},
  url       = {https://mlanthology.org/neurips/2020/ghazi2020neurips-differentially/}
}