Improved Lower Bound for Differentially Private Facility Location

arXiv:2403.04874v1 Announce Type: cross
Abstract: 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 $\epsilon$-DP algorithm is $O\left(\frac{\log n}{\sqrt{\epsilon}}\right)$ due to Cohen-Addad et al. [AISTATS 2022] where $n$ denote the size of the metric space, meanwhile the best known lower bound is $\Omega(1/\sqrt{\epsilon})$ [NeurIPS 2019].
In this short note, we give a lower bound of $\tilde{\Omega}\left(\min\left\{\log n, …

algorithm arxiv called cs.cr cs.ds current facility location log private problem soda super