On Facility Location Problem in the Local Differential Privacy Model

Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboradi, Shi Li, Di Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish (US)
Title of host publication25th International Conference on Artificial Intelligence and Statistics
StatePublished - 2022


Dive into the research topics of 'On Facility Location Problem in the Local Differential Privacy Model'. Together they form a unique fingerprint.

Cite this