Facility Location Problem in Differential Privacy Model Revisited
This work addresses privacy-preserving optimization for facility location, offering improved bounds but is incremental over prior results.
The paper tackles the uncapacitated facility location problem under differential privacy, achieving an O(1/ε) approximation ratio for HST metrics and O(log n/ε) for general metrics, while proving a lower bound of Ω(1/√ε) for HST metrics.
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 $ε$-DP algorithm that achieves an $O(\frac{1}ε)$(expected multiplicative) approximation ratio; this implies an $O(\frac{\log n}ε)$ 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 $ε$-DP algorithm is lower bounded by $Ω(\frac{1}{\sqrtε})$, 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 $ε$ can not be removed or greatly improved. Our novel methods and techniques for both the upper and lower bound may find additional applications.