Facility Location Problem in Differential Privacy Model Revisited
Facility Location Problem in Differential Privacy Model Revisited
复制标题
DOI：
--
复制
发表时间：
2019-10
期刊：
影响因子：
--
通讯作者：
Yunus Esencayi;Marco Gaboardi;Shi Li;Di Wang
中科院分区：
文献类型：
--
作者：
Yunus Esencayi;Marco Gaboardi;Shi Li;Di Wang
在本文中，我们研究了设施的设施位置问题（DP），设施成本均匀。具体而言，我们首先表明，在层次上分离的树（HST）指标和Gupta ET中引入的超级设定输出设置下。 al。，有一个$ \ epsilon $ -DP算法可以实现$ o（\ frac {1} {\ epsilon}）$（预期乘法）近似值；这意味着$ o（\ frac {\ log n} {\ epsilon}）$近似值的一般度量案例，其中$ n $是输入度量的大小。这些界限改善了Gupta ET给出的最著名的结果。 al。特别是，我们的HST-Metrics的近似值与$ N $无关，并且通用指标的比率与输入度量的纵横比无关。负面的一面，我们表明，即使在HST Metrics on Metrics on Metrics on Metrics on Metrics on Betrics y，我们也表明，任何$ \ epsilon $ -dp算法的近似值均由$ \ omega（\ frac {1} {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ sqrt {\ frac {1} {在超级设定的输出设置下，设施成本均匀。下边界表明，HST指标对$ \ epsilon $的近似值的依赖性无法删除或大大改善。我们针对上和下边界的新型方法和技术可能会找到其他应用。
In this paper we study the facility location problem in the model of differential privacy (DP) with uniform facility cost. Specifically, we first show that under the hierarchically well-separated tree (HST) metrics and the super-set output setting that was introduced in Gupta et. al., there is an $\epsilon$-DP algorithm that achieves an $O(\frac{1}{\epsilon})$(expected multiplicative) approximation ratio; this implies an $O(\frac{\log n}{\epsilon})$ approximation ratio for the general metric case, where $n$ is the size of the input metric. These bounds improve the best-known results given by Gupta et. al. In particular, our approximation ratio for HST-metrics is independent of $n$, and the ratio for general metrics is independent of the aspect ratio of the input metric. On the negative side, we show that the approximation ratio of any $\epsilon$-DP algorithm is lower bounded by $\Omega(\frac{1}{\sqrt{\epsilon}})$, even for instances on HST metrics with uniform facility cost, under the super-set output setting. The lower bound shows that the dependence of the approximation ratio for HST metrics on $\epsilon$ can not be removed or greatly improved. Our novel methods and techniques for both the upper and lower bound may find additional applications.