On Facility Location Problem in the Local Differential Privacy Model

We study the facility location problem under the constraints imposed by local differential privacy (LDP). Recently, Gupta et al. (2010) and Esencayi et al. (2019) proposed lower and upper bounds for the problem on the central differential privacy (DP) model where a trusted curator first collects all data and processes it. In this paper, we focus on the LDP model, where we protect a client's participation in the facility location instance. Under the HST metric, we show that there is a non-interactive epsilon-LDP algorithm achieving O(n(1/4)/epsilon(2))-approximation ratio, where n is the size of the metric. On the negative side, we show a lower bound of Omega(n(1/4)/root epsilon) on the approximation ratio for any non-interactive epsilon-LDP algorithm. Thus, our results are tight up to a polynomial factor of epsilon. Moreover, unlike previous results, our results generalize to non-uniform facility costs.