Facility location problem in differential privacy model revisited

Yunus Esencayi, Marco Gaboardi, Shi Li, Di Wang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

In this paper we study the uncapacitated facility location problem in the model of differential privacy (DP) with uniform facility cost. Specifically, we first show that, under the hierarchically well-separated tree (HST) metrics and the super-set output setting that was introduced in [8], there is an e-DP algorithm that achieves an O(1/e) (expected multiplicative) approximation ratio; this implies an O(log n/e ) approximation ratio for the general metric case, where n is the size of the input metric. These bounds improve the best-known results given by [8]. In particular, our approximation ratio for HST-metrics is independent of n, and the ratio for general metrics is independent of the aspect ratio of the input metric. On the negative side, we show that the approximation ratio of any e-DP algorithm is lower bounded by ?(1/ve ), even for instances on HST metrics with uniform facility cost, under the super-set output setting. The lower bound shows that the dependence of the approximation ratio for HST metrics on e can not be removed or greatly improved. Our novel methods and techniques for both the upper and lower bound may find additional applications.
Original languageEnglish (US)
Title of host publicationAdvances in Neural Information Processing Systems
PublisherNeural information processing systems foundation
StatePublished - Jan 1 2019
Externally publishedYes

Cite this