Timezone: »
Poster
Facility Location Problem in Differential Privacy Model Revisited
Yunus Esencayi · Marco Gaboardi · Shi Li · Di Wang
Thu Dec 12 10:45 AM  12:45 PM (PST) @ East Exhibition Hall B + C #91
In this paper we study the facility location problem in the model of differential privacy (DP) with uniform facility cost. Specifically, we first show that under the hierarchically wellseparated tree (HST) metrics and the superset 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 bestknown results given by Gupta et. al. In particular, our approximation ratio for HSTmetrics 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 superset 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.
Author Information
Yunus Esencayi (State University of New York at Buffalo)
Marco Gaboardi (Univeristy at Buffalo)
Shi Li (University at Buffalo)
Di Wang (State University of New York at Buffalo)
More from the Same Authors

2019 Poster: Privacy Amplification by Mixing and Diffusion Mechanisms »
Borja Balle · Gilles Barthe · Marco Gaboardi · Joseph Geumlek 
2018 Poster: Distributed $k$Clustering for Data with Heavy Noise »
Shi Li · Xiangyu Guo 
2018 Spotlight: Distributed $k$Clustering for Data with Heavy Noise »
Shi Li · Xiangyu Guo 
2018 Poster: Empirical Risk Minimization in Noninteractive Local Differential Privacy Revisited »
Di Wang · Marco Gaboardi · Jinhui Xu 
2018 Poster: Approximation algorithms for stochastic clustering »
David Harris · Shi Li · Aravind Srinivasan · Khoa Trinh · Thomas Pensyl 
2018 Poster: Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences »
Borja Balle · Gilles Barthe · Marco Gaboardi 
2017 Poster: Differentially Private Empirical Risk Minimization Revisited: Faster and More General »
Di Wang · Minwei Ye · Jinhui Xu