Facility Location Problem in Differential Privacy Model Revisited
  In this paper we study the uncapacitated 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.
