Details

Autor(en) / Beteiligte

• Manurangsi, Pasin

Titel

Improved lower bound for differentially private facility location

Ist Teil von

• Information processing letters, 2025-01, Vol.187, p.106502, Article 106502

Ort / Verlag

Elsevier B.V

Erscheinungsjahr

2025

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• We consider the differentially private (DP) facility location problem in the so called super-set output setting proposed by Gupta et al. [13]. The current best known expected approximation ratio for an ϵ-DP algorithm is O(log⁡nϵ) due to Cohen-Addad et al. [3] where n denote the size of the metric space, meanwhile the best known lower bound is Ω(1/ϵ)[8]. In this short note, we give a lower bound of Ω˜(min⁡{log⁡n,log⁡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. •Study facility location problem under differential privacy constraints in the super-set output model.•Previous best algorithm gave O(log⁡n/ϵ)-approximation and previous lower bound on the approximation ratio was O(1/ϵ).•We give Ω˜(min⁡{log⁡n,log⁡n/ϵ}) on the approximation ratio; this is the first known lower bound that grows with n.