


























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\left(\frac{\log n}{\sqrtε}\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 $Ω(1/\sqrtε)$ [NeurIPS 2019]. In this short note, we give a lower bound of $\tildeΩ\left(\min\left\{\log n, \sqrt{\frac{\log n}ε}\right\}\right)$ 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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。