Improved lower bound for differentially private facility location

We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [13]. The current best known expected approximation ratio for an epsilon-DP algorithm is O(log n/root epsilon) due to Cohen-Addad et al. [3] where.. denote the size of the metric space, meanwhile the best known lower bound is Omega(1/root epsilon) [8]. In this short note, we give a lower bound of (Omega) over tilde (min {log n, root log n/epsilon}) on the expected approximation ratio of any epsilon-DP algorithm, which is the first evidence that the approximation ratio has to grow with the size of the metric space.