We design new differentially private algorithms for the Euclidean k-means
problem, both in the centralized model and in the local model of differential
privacy. In both models, our algorithms achieve significantly improved error
guarantees than the previous state-of-the-art. In addition, in the local model,
our algorithm significantly reduces the number of interaction rounds.
Although the problem has been widely studied in the context of differential
privacy, all of the existing constructions achieve only super constant
approximation factors. We present, for the first time, efficient private
algorithms for the problem with constant multiplicative error. Furthermore, we
show how to modify our algorithms so they compute private corsets for k-means
clustering in both models.

本研究针对欧几里得 k 均值问题，设计了新的差分隐私算法，其在中心模型和本地模型中均获得了显著提高的误差保证，并且还能计算私有 corsets 来处理 k 均值聚类问题。

带有恒定乘性误差的差分隐私 k 均值算法

Differentially Private k-Means with Constant Multiplicative Error

The Euclidean $k$-means problem is a classical problem that has been
extensively studied in the theoretical computer science, machine learning and
the computational geometry communities. In this problem, we are given a set of
$n$ points in Euclidean space $R^d$, and the goal is to choose $k$ centers in
$R^d$ so that the sum of squared distances of each point to its nearest center
is minimized. The best approximation algorithms for this problem include a
polynomial time constant factor approximation for general $k$ and a
$(1+\epsilon)$-approximation which runs in time $poly(n) 2^{O(k/\epsilon)}$. At
the other extreme, the only known computational complexity result for this
problem is NP-hardness [ADHP'09]. The main difficulty in obtaining hardness
results stems from the Euclidean nature of the problem, and the fact that any
point in $R^d$ can be a potential center. This gap in understanding left open
the intriguing possibility that the problem might admit a PTAS for all $k,d$.
In this paper we provide the first hardness of approximation for the
Euclidean $k$-means problem. Concretely, we show that there exists a constant
$\epsilon > 0$ such that it is NP-hard to approximate the $k$-means objective
to within a factor of $(1+\epsilon)$. We show this via an efficient reduction
from the vertex cover problem on triangle-free graphs: given a triangle-free
graph, the goal is to choose the fewest number of vertices which are incident
on all the edges. Additionally, we give a proof that the current best hardness
results for vertex cover can be carried over to triangle-free graphs. To show
this we transform $G$, a known hard vertex cover instance, by taking a graph
product with a suitably chosen graph $H$, and showing that the size of the
(normalized) maximum independent set is almost exactly preserved in the product
graph using a spectral analysis, which might be of independent interest.

本研究采用图谱分析的方法，证明了欧几里得 k-means 问题的近似难度对于所有的 k 和 d 都是 NP 难的，同时发现当前最佳难度结果可以被推广到三角免费图中。