Reviews: Differentially Private k-Means with Constant Multiplicative Error

The paper considers k-means under differential privacy. The main idea of differential privacy (applied to k-means) is that changing one point in the input should not significantly change the centers that are computed. This immediately means that any approximation algorithm for the differentially private k-means problem needs to have additive error: The introduction includes a simple example of points in k locations ( optimum has zero cost). Now when moving one of these points to a different location, the centers may not change significantly; ergo one of the solutions has to have a large additive error; basically an error of D 2 where D is the largest pairwise distance. Thus, a common approach for this problem is to compute an approximation that is both multiplicative and additive. The best known result prior to this paper achieves a quality of O(k)*OPT O (d 0.51 k 1.51).