Locally Private k-Means in One Round
  We provide an approximation algorithm for k-means clustering in the one-round
(aka non-interactive) local model of differential privacy (DP). This algorithm
achieves an approximation ratio arbitrarily close to the best non private
approximation algorithm, improving upon previously known algorithms that only
guarantee large (constant) approximation ratios. Furthermore, this is the first
constant-factor approximation algorithm for k-means that requires only one
round of communication in the local DP model, positively resolving an open
question of Stemmer (SODA 2020). Our algorithmic framework is quite flexible;
we demonstrate this by showing that it also yields a similar near-optimal
approximation algorithm in the (one-round) shuffle DP model.
