On Facility Location Problem in the Local Differential Privacy Model

Vincent Cohen-Addad, Yunus Esencayi, Chenglin Fan, Marco Gaboradi, Shi Li, Di Wang
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:3914-3929, 2022.

Abstract

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}/\sqrt{\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-cohen-addad22a, title = { On Facility Location Problem in the Local Differential Privacy Model }, author = {Cohen-Addad, Vincent and Esencayi, Yunus and Fan, Chenglin and Gaboradi, Marco and Li, Shi and Wang, Di}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {3914--3929}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/cohen-addad22a/cohen-addad22a.pdf}, url = {https://proceedings.mlr.press/v151/cohen-addad22a.html}, abstract = { 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}/\sqrt{\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. } }
Endnote
%0 Conference Paper %T On Facility Location Problem in the Local Differential Privacy Model %A Vincent Cohen-Addad %A Yunus Esencayi %A Chenglin Fan %A Marco Gaboradi %A Shi Li %A Di Wang %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-cohen-addad22a %I PMLR %P 3914--3929 %U https://proceedings.mlr.press/v151/cohen-addad22a.html %V 151 %X 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}/\sqrt{\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.
APA
Cohen-Addad, V., Esencayi, Y., Fan, C., Gaboradi, M., Li, S. & Wang, D.. (2022). On Facility Location Problem in the Local Differential Privacy Model . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:3914-3929 Available from https://proceedings.mlr.press/v151/cohen-addad22a.html.

Related Material