论文标题
差异私有聚类：紧密近似比
Differentially Private Clustering: Tight Approximation Ratios
论文作者
论文摘要
我们研究差异私人聚类的任务。对于几个基本的聚类问题，包括欧几里得密集球，1群，K-均值和K-Median，我们提供了有效的差异性私有算法，这些算法基本上与任何非私有算法可以获得的近似值基本相同，而仅刺激的小添加误差。这改善了现有的有效算法，该算法仅达到一些较大的恒定近似因子。 我们的结果还意味着针对样品和汇总隐私框架的改进算法。此外，我们表明，可以使用1群算法中使用的一种工具来获得更快的量子算法，以在中等数量的尺寸中获得近距台。
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.
