Locally Private $k$-Means Clustering with Constant Multiplicative Approximation and Near-Optimal Additive Error

Anamay Chaturvedi, Matthew Jones, Huy L. Nguyen

Given a data set of size $n$ in $d^{\prime }$-dimensional Euclidean space, the $k$-means problem asks for a set of $k$ points (called centers) so that the sum of the ${\ell }_2^2$-distances be…