Differentially Private Clustering via Maximum Coverage
This addresses privacy-preserving clustering for data analysts, though it appears incremental as it builds on existing differentially private clustering approaches.
The paper tackles differentially private clustering for k-medians and Euclidean k-means problems, presenting polynomial algorithms that achieve constant multiplicative error with lower additive error than previous state-of-the-art methods.
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.