Improved Lower Bound for Differentially Private Facility Location

2024/03/07 by Pasin Manurangsi, Manurangsi, Pasin · 1 citation
Business, Management and Accounting · #Facility Location and Emergency Management

paper · pdf · doi:10.48550/arxiv.2403.04874

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 ε-DP algorithm is O((log 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 Ω(min\log n, √\fraclog 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.

Cited by

• Facility Location Problem under Local Differential Privacy without Super-set Assumption

Related

• Facility Location Problem in Differential Privacy Model Revisited
• Facility Location Problem under Local Differential Privacy without Super-set Assumption
• A Systematic Approach to Bound Factor-Revealing LPs and its Application to the Metric and Squared Metric Facility Location Problems
• Facility Location on High-dimensional Euclidean Spaces
• Differentially Private Partial Set Cover with Applications to Facility Location