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. SODA 2010. The current best known expected approximation ratio for an -DP algorithm is O (n) due to Cohen-Addad et al. AISTATS 2022 where n denote the size of the metric space, meanwhile the best known lower bound is (1/) NeurIPS 2019. In this short note, we give a lower bound of (\ n, { n{}\}) on the expected approximation ratio of any -DP algorithm, which is the first evidence that the approximation ratio has to grow with the size of the metric space.