NeurIPS 2020oral61 citations
Differentially Private Clustering: Tight Approximation Ratios
Badih Ghazi, Ravi Kumar, Pasin Manurangsi
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.
BibTeX
@inproceedings{NEURIPS2020_299dc35e,
author = {Ghazi, Badih and Kumar, Ravi and Manurangsi, Pasin},
booktitle = {Advances in Neural Information Processing Systems},
editor = {H. Larochelle and M. Ranzato and R. Hadsell and M.F. Balcan and H. Lin},
pages = {4040--4054},
publisher = {Curran Associates, Inc.},
title = {Differentially Private Clustering: Tight Approximation Ratios},
url = {https://proceedings.neurips.cc/paper_files/paper/2020/file/299dc35e747eb77177d9cea10a802da2-Paper.pdf},
volume = {33},
year = {2020}
}