Improved Lower Bound for Differentially Private Facility Location
<|reference_start|>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 $\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, \sqrt{\frac{\log n}{\epsilon}}\right\}\right)$ 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.<|reference_end|>
@article{manurangsi2024improved,
    title={Improved Lower Bound for Differentially Private Facility Location},
    author={Pasin Manurangsi},
    journal={arXiv preprint arXiv:2403.04874},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.04874},
    primaryClass={cs.DS cs.CR}
}