  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.
