Differentially Private Partial Set Cover with Applications to Facility Location

1 Introduction

Data privacy is a fundamental challenge in many real world applications of data-driven decision making where there is a risk of inadvertently revealing private information. Differential privacy, introduced in [Dwork et al., 2006], has emerged as a widely accepted formalization of privacy, which gives rigorous parameterized guarantees on the privacy loss while simultaneously enabling non-trivial utility in algorithmic and statistical analysis. Differential privacy is defined in terms of datasets which differ by one individual, called neighboring datasets, and requires that the output of a mechanism is (approximately) indistinguishable when run on any two neighboring datasets. Formally, it is defined as:

Definition 1.1. M : X n → Y is (ϵ, δ)-differentially private if for any neighboring datasets X, X′ ∈ X n and S ⊆ Y,

If δ = 0, we say M is ϵ-differentially private.

Differentially private algorithms have now been developed for a number of problems ranging from statistics [Canonne et al., 2020; Brown et al., 2021], machine learning and deep learning [Lee and Kifer, 2018; Ghazi et al., 2021], social network analysis [Nissim et al., 2007; Hay et al., 2009; Karwa et al., 2011], and combinatorial optimization [Mitrovic et al., 2017; Esencayi et al., 2019; Nguyen and Vullikanti, 2021]. See [Dwork and Roth, 2014; Vadhan, 2017] for a survey on the techniques used.

In this work, we consider a fundamental problem in combinatorial optimization: the Set Cover problem [Williamson and Shmoys, 2011], which involves choosing the smallest subset of a set system S = {S1, . . . , Sm} ⊂ 2U that covers a universe U = {u1, . . . , un}. In many settings, the elements of the universe U are private (e.g., clients wish to be private in facility location problems). [Gupta et al., 2010] first studied the problem of Set Cover with privacy, and showed that outputting an explicit solution to Set Cover has strong hardness results, even for the special case of Vertex Cover: any differentially private algorithm must output a set cover of size m- 1 with probability 1 on any input, a useless result.

As a result, the authors designed a mechanism which outputs an implicit set cover via a privacy-preserving set of instruction for the elements to reconstruct the set cover. While the implicit solutions are useful in some limited settings, it cannot replace the explicit solutions needed in many important applications, such as public health [Eubank et al., 2004; Li et al., 2022]. In particular, explicit solutions are necessary when using a Set Cover algorithm as a subroutine when solving a more complicated problem. As a result, we turn to the Partial Set Cover problem, where we only need to cover a ρfraction of the elements in U, for ρ ∈ (0, 1). Due to the space limit, we present our core results in the main paper and defer some analyses and experimental results to the Appendix. We maintain a full, updated version of this work here 1 .

1 https://arxiv.org/abs/2207.10240

Our primary contributions are:

• We observe that the impossibility results for outputting an explicit set cover under differential privacy are alleviated when considering the Partial Set Cover problem. When the number sets isn't too large (i.e., m = O(n)), we give a O(log2 (m) log(1/δ)/ϵ(1-ρ))-approximation algorithm (see Theorem 2.4). Alternatively, when the optimal partial set cover isn't too large (i.e., OPT ≲ nϵ log3 n log(1/δ) ), we give aO(log( 1 (1-ρ) ))-pseudo approximation algorithm (see Theorem 2.6). Note that both of our guarantees break down as ρ → 1.
• To illustrate the importance of explicit solutions, we use our differentially private Partial Set Cover algorithm as a subroutine to give a differentially private approximation algorithm for a vaccine distribution problem which in particular, generalizes k-supplier with outliers. We emphasize that this is the first differentially private algorithm for k-supplier type problems with non-trivial approximation guarantees, which was thought to be impossible due to the high sensitivity of min-max objectives.
• Finally, we evaluate the our private algorithms on real life datasets for set cover and vaccine distribution, and observe a good privacy-utility tradeoff: the empirical approximation factors are much better than the worst case bounds we give in our theorem statements. We view the vaccine distribution problem as a concrete practical contribution of our work (see Figure 1 for an example).

1.1 RelatedWork

The Set Cover problem and its various generalizations have been studied by combinatorial optimization community for several decades [Wolsey, 1982; Alon et al., 2003]. For the simplest version, there exists a greedy algorithm which achieves a (logn + 1)-approximation which is best possible unless P=NP [Moshkovitz, 2015]. [Gupta et al., 2010]

first considered the Set Cover problem under differential privacy, showing impossibility results of outputting explicit set covers. They then gave approximation algorithms via outputting implicit set covers, which we argue is insufficient for many applications. The only other work which outputs explicit set covers under differential privacy is [Hsu et al., 2014], which approach the set cover problem via private linear programming. They give approximation guarantees but ignore O(OPT2 · polylog(n, 1/δ)) elements. One of our algorithms also has guarantees of this form, but ignores only ρn elements, which is better when the size of the optimal set cover is larger. We also give a true approximation for Partial Set Cover, which is the first in the literature.

Also directly related to our work are the differentially private facility location problems, which [Gupta et al., 2010] also first considered. For the uniform facility location problem, they showed that a Ω(√n)-approximation is needed under differential privacy, an essentially useless result, and devised a way to implicitly output the facilities. [Esencayi et al., 2019] built upon their work, improving the approximation guarantees to O( logn ϵ ) for general metrics. [Cohen-Addad et al., 2022b] considered the facility location problem under the local differential privacy model, gave tight approximation algorithms up to polynomial factors of ϵ. A particular interesting quality of their algorithms is that it extends to non-uniform facility location. [Gupta et al., 2010] also considered the k-median problem, and developed approximation algorithms which guaranteed that the service cost is at most 6 · OPT + O( k2 log2 n ϵ ). Since then, there has been an abundance of work on this problem improving the approximation guarantees, practical performance, and efficiency of the differentially private algorithms [Balcan et al., 2017; Ghazi et al., 2020; Blocki et al., 2021; Jones et al., 2021; Cohen-Addad et al., 2022a]. Despite the abundance of work on facility location-type problems, k-supplier remains untouched; our work is the first to overcome impossibility results and give approximation guarantees for the problem.

1.2 Differential Privacy Background

In our algorithms, we will make extensive use of the following basic mechanisms and properties, the proofs of which can be found in [Dwork and Roth, 2014]. The post-processing and composition properties enable us to easily combine smaller differentially private mechanisms to create a more complicated one:

Theorem 1.2. Let M1 : X n → Y1 andM2 : X n → Y2 be (ϵ1, δ1) and (ϵ2, δ2)-differentially private algorithms, respectively. The following properties hold:

• post-processing: Let f : Y1 → Z be an arbitrary (potentially randomized) mapping. Then f ◦M1 : X n → Z is (ϵ1, δ1)-differentially private.
• composition: Let M : X n → Y1 × Y2 be defined as M = (M1,M2). Then M is (ϵ1 + ϵ2, δ1 + δ2)- differentially private.

We next state the Laplace Mechanism which, by adding Laplace noise, provides a simple way to privately output a statistic that depends on a private database:

Theorem 1.3. Given a function f : X n → Rk , the ℓ1sensitivity is defined as ∆f = maxx∼x′ ∥f(x) - f(x′ )∥1. The Laplace Mechanism, given the function f : X n → Rk , outputs f(x)+(Y1, . . . , Yk), where Yi are i.i.d. random variables drawn from Lap(∆f /ϵ). We claim the Laplace Mechanism is ϵ-differentially private.

Finally, we state the Exponential Mechanism which approximately optimizes the utility function over some set of candidates choices R while preserving privacy:

Definition 1.4. Given a utility function u : X n ×R → R, let ∆u = maxr∈R maxx∼x′ |u(x, r)-u(x′ , r)| be the sensitivity of u, where x, x′ are neighboring datasets. The exponential mechanism M(x, u, R) outputs an element r ∈ R with probability ∝ exp( ϵu(x,r) 2∆u ).

Theorem 1.5. The exponential mechanism is ϵ-differentially private. Furthermore, if we fix a dataset x and let OPT = maxr∈Ru(x, r), we have Pr[u(x,M(x, u,R)) ≤ OPT - 2∆u ϵ (ln |R| + t)] ≤ e-t .

2 Differentially Private Partial Set Cover

Formally, we wish to solve the following problem:

Definition 2.1. Let U = {u1, . . . , un} be the universe of elements and let S = {S1, . . . , Sm} be a set system where each Si ⊆ U and ⋃mi=1 Si = U. Finally, let ρ < 1 be the covering requirement. The Partial Set Cover problem asks for the minimal size subset {π1, . . . , πk} of S such that | ⋃ki=1 πi| ≥ ρ|U| (i.e., the subset covers a ρ fraction of U).

For differential privacy, we consider two Partial Set Cover instances neighboring if the set systems (U1, S1) and (U2, S2) are two neighboring datasets if they differ by exactly one element u in the universe and the sets Si1 ∈ S1 and Si2 ∈ S2 differ only by u (or are the same). Note that our definition of privacy can recover the one considered in [Gupta et al., 2010] and [Hsu et al., 2014] as a special case, but is in general stronger. We elaborate on this subtlety further in the Appendix.

At first glance, our (and [Gupta et al., 2010]'s) definition of neighboring datasets for (Partial) Set Cover may not be entirely intuitive. As an example of an application where such a privacy definition makes sense, let's consider the problem studied by [Eubank et al., 2004] of placing sensors in peoplelocation graphs to detect the spread of a disease. Formally, we have a bipartite graph where nodes in one part of the graph represent locations and nodes in the other part represent people. An edge exists between a person and a location if the person visits that location. We wish to place sensors at the locations so that infected individuals can be detected. Since placing sensors is an expensive process, we wish to place the fewest sensors as possible to cover a ρ-fraction of the population. This can be formulated as a Partial Set Cover problem. For this example, our notion of privacy corresponds to node privacy for people in the graph. In addition to this example, we show in the following section that our privacy definition here also lines up nicely with client-privacy in facility location problems when using Partial Set Cover to solve ksupplier with outliers.

In the following subsections, we'll present our algorithms for differentially private Partial Set Cover. Since Partial Set Cover is NP-Hard, we will focus on giving approximation algorithms while preserving differential privacy. We say an algorithm gives an α-approximation to the optimal solution if it outputs a partial set cover of size at most α · OPT, where OPT is the size of an optimal partial set cover.

2.1 A Private Variant of the Greedy Algorithm

The general outline of our first algorithm is as follows: we use a private version of the classical greedy algorithm for Partial Set Cover to output a permutation of the sets π1, . . . , πm. Then, we use an offline implementation of the AboveThreshold mechanism to choose a threshold k such that π1, . . . , πk covers a ρ fraction of the elements.

Input: Set system (U, S), covering requirement ρ, and privacy parameters (ϵ, δ)

pick set S ∈ Si with probability ∝ exp(ϵ′ |S ∩ Ui|).

let πi ← S, Ui+1 ← Ui - S, Si+1 ← Si - {S}.

end for

let k be first index such that γk ≥ ˆ T .

Output: (π, k) //π1, . . . , πk is a set cover for (U, S)

Lemma 2.2. Let k∗ be the first index such that π1, . . . , πk∗

Proof. For iteration i ∈ [m], let Li be the size of the set which covers the most additional elements (i.e., Li = maxS∈Si |S∩ Ui|). For an iteration where Li ≥ 6 lnm/ϵ′ , the probability of selecting a set which covers less than Li - 3 lnm/ϵ′ is at most 1 m2 . Hence, over all iterations where Li ≥ 6 lnm/ϵ′ , we will choose a set which covers at least Li/2 elements with probability at least 1 - 1m . By a standard argument [Williamson and Shmoys, 2011], this will only use at most OPT · lnn sets. Consider the last iteration t such that Lt ≥ 6 lnm/ϵ′ . If the number of elements covered through iteration t is at least ρ′n, then we are done. The rest of the proof deals with the case where less than ρ′n are covered.

Next, we analyze what happens when Lj < 6 lnm/ϵ′ for j = t + 1, . . . ,m. The utility guarantees of the exponential mechanism are essentially useless from this iteration onwards. Notice that the number of remaining elements |Uj| is at most OPT · |Lj|. Unfortunately, we cannot claim that each set chosen covers at least one element; this is simply not true. Instead, we analyze the probability that a set covering at least one element is chosen. Let ρ′ = ρ+1 2 and note that ρ′ < 1 and ρ′n ≥ ρn + 24 logm ϵ for sufficiently large n. Since there are at least (1-ρ′ )n uncovered elements remaining and m = O(n), there necessarily exists some constant ρ′′ such that the probability of not covering anything is at most [1-(1-ρ′′ )]. Thus, the probability of not covering anything over the course of 2 lnm 1-ρ′′ iterations is at most

where we used 1 - x ≤ exp(-x). Thus, each of the |Uj| remaining elements is covered using at most 2 lnm 1-ρ′′ sets, with probability at least 1- 1m . Since there are at most OPT · |Lj| elements remaining which need to be covered, at most OPT · 2 ln(m)2 ϵ′ (1-ρ′′ ) sets are used.

Lemma 2.3. (Lemma A.1) With probability 1 -O ( 1m ), the threshold k satisfies |π1 ∪ · · · ∪ πk| ∈ [ρn, ρn + 24 log m/ϵ].

Theorem 2.4. For ϵ ∈ (0, 1), δ < 1e , and m = O(n), the following are true for Partial Set Cover

• Algorithm 1 preserves (2ϵ, δ)-differential privacy.
• With probability 1 - O( 1m ), Algorithm 1 is an O ( ln(m)2 ln(1/δ) ϵ(1-ρ) )-approximation algorithm.

Proof. Let's first consider the privacy. Outputting the permutation of sets was shown to be (ϵ, δ)-differentially private in [Gupta et al., 2010]. Our mechanism for outputting the threshold k can be viewed as an offline implementation of the AboveThreshold mechanism from [Dwork and Roth, 2014]. Since switching to a neighboring set system changes the number of elements covered by a family of sets by at most 1, the analysis of [Dwork and Roth, 2014] applies and outputting the threshold is (ϵ, 0)-differentially private. By basic composition of adaptive mechanisms [Dwork and Roth, 2014], we have (2ϵ, δ)-differential privacy.

Now, we turn to the utility guarantee. Consider the threshold k selected; by Lemma 2.3, the threshold is such that |π1 ∪ · · · ∪ πk| in the interval [ρn, ρn + 24 logm ϵ ] with probability at least 1 - 1m . Hence, it is a ρn-partial cover and by Lemma 2.2, uses at most O ( ln(m)2 ln(1/δ) ϵ(1-ρ) ) · OPT sets.

Remark 1. In Theorem 2.4 (and in future Theorems 2.6 and 3.2)), we can reduce the probability of failure to an arbitrary polynomial in m by losing constant factors in the approximation guarantee.

2.2 Algorithm viaMaximumCoverage

In this section, we give another algorithm for Partial Set Cover under differential privacy. Our algorithm here will give a pseudo-approximation for the problem (i.e., our approximation factor will be with respect to the optimal Set Cover solution instead of the optimal Partial Set Cover solution). Such a guarantee is similar to the one given in [Hsu et al., 2014]. To give our algorithm, we first need to define the Differentially Private Maximum Coverage problem:

Definition 2.5. Let U = {u1, . . . , un} be the universe of elements and let S = {S1, . . . , Sm} be a set system where each Si ⊆ U and ⋃mi=1 Si = U. Finally, let k be the budget. The Maximum Coverage problem asks us to find a size k subset {π1, . . . , πk} of S such that | ⋃ki=1 πi| is maximized.

As in the Partial Set Cover problem, we view the elements of the universe as the private information and we view two set systems as neighbors if they differ by exactly one element u in the universe. Since the objective here is submodular and monotone [Williamson and Shmoys, 2011], we can apply the following result from [Mitrovic et al., 2017] for submodular maximization. We remark that the result we state is stronger than the one given in [Mitrovic et al., 2017], since we can use a specialized privacy analysis for maximum coverage (like in [Gupta et al., 2010]) which is not possible for general submodular functions. This has shown up in other works such as [Jones et al., 2021].

Lemma 2.6. There exists an (ϵ, δ)-differentially private algorithm for the maximum coverage problem which such that the expected number of elements covered is (1 - 1e ) OPT -

The main idea for our algorithm for Partial Set Cover is that under some restrictions on the set system and budget, the Maximum Coverage problem can be approximated within a constant factor under differential privacy via the algorithm in Lemma 2.6. Then, iteratively applying the algorithm for the maximum coverage problem with budget k set to the size of the optimal Partial Set Cover suffices to obtain a good approximation algorithm for Partial Set Cover.

Lemma 2.7. (Lemma A.2) There exists an (2ϵ, δ)- differentially private algorithm for the maximum coverage problem such that for some constant C, if we have

then the algorithm is a 0.15-approximation with probability 1 - O( 1n ), where ϵ0 = ϵ 2 ln(e ln(n)/δ ln(1+α)) .

Given this result, we can state our algorithm for Partial Set Cover. For simplicity of notation, let's denote the Algorithm referenced in Lemma 2.7 by MAXCOVER(U, S, k, ϵ, δ). As mentioned before, the idea is to guess the size of the optimal Partial Set Cover via binary search. Then, assuming we have OPT, we can run MAXCOVER approximately O(log(1 - ρ)) times in order to cover ρn elements. Though the idea is very simple, there are many subtleties in the algorithm due to privacy. First, our binary search must guarantee that our guess OPT′ is at most upper; this is because the guarantee in Lemma 2.7 only applies when the budget isn't too large. Additionally, when binary searching for OPT, we need to decide if the guess is too large or too small, based on the number of elements covered by the output. However, we cannot do this directly since the elements are considered private; as a result, we need to add Laplace noise before making the comparison. This makes the analysis slightly more complicated.

Algorithm 2 MMaxCoverage(U , S, ρ, ϵ, δ)

Input: Set system (U, S), covering requirement ρ, privacy parameters (ϵ, δ)

Binary Search on {1, . . . , upper}, and let the current guess be OPT′

run MAXCOVER(Ui, Si,OPT′ , ϵ′ , δ′ ) to obtain sets

let γ be the number of elements covered by SOL

if ˆ γ ≥ ρn increase OPT′ ; otherwise, decrease OPT′ Output: SOL for minimum OPT′ satisfying ˆ γ ≥ ρn

γ = γ + log n ϵ′ +Lap(1/ϵ′ )

Theorem 2.8. Algorithm 2 is (ϵ, δ)-DP. Furthermore, assuming the optimal set cover has size OPT ≤ C(1- ρ2 )nϵ0 ln3 (n) , where C is from Lemma 2.7 and ϵ0 = O ( ϵ/t ln ln(n)+ln(t/δ) ), Algorithm 2 outputs a (1 - ρ)-Partial Set Cover using at most O(log( 1 1-ρ )) · OPT sets with probability 1 - ˜O( 1n ).

Proof. First, let's consider the privacy guarantee. For each iteration of the binary search, we run MAXCOVER t times. By basic composition, we this is (tϵ′ , tδ′ )-differentially private. Additionally, ˆ γ is the output of the Laplace Mechanism, so it is (tϵ′ , 0)-differentially private. The binary search takes at most log2(upper) ≤ log2(n) iterations to converge, so (2ϵ, δ)-differential privacy follows by basic composition once again. Finally, the outputted solution SOL is (2ϵ, δ)- differentially private by post-processing.

Now, we will turn to the utility guarantee. Let ρ′ = ρ+1 2 , β = 0.15, and let us first consider the algorithm when our guess OPT′ is at least OPT. We claim that running MAXCOVER t times, as in Algorithm 2, covers at least ρ′n ≥ ρn + 2 log n ϵ′ elements. Since the output of the Laplace mechanism ˆ γ will be at least ρn with probability at least 1- 1n , the binary search will converge to some OPT′ ≤ OPT. Now, consider the partial set cover output by the algorithm; we know that the number of sets used is t · OPT′ ≤ t · OPT, hence a t-approximation. Next, we will prove our claim.

If at any iteration i < t, we have ρ′n elements are covered by the previously selected sets, we are done. Suppose there remains at least (1-ρ′ )n elements uncovered at all iterations i ≤ t; we will show that ρ′n elements are covered after iteration t. By definition of OPT and the fact that OPT′ ≥ OPT, there exists OPT′ sets which cover the remaining uncovered elements. Thus, when OPT is suitably small as in the theorem statement, running MAXCOVER always covers at least an α-fraction of the remaining elements, leaving a (1 - α)- fraction of the remaining elements uncovered. By algebra, running MAXCOVER t times suffices to guarantee that at most (1 - ρ′ )n elements remain uncovered.

Remark 2. We emphasize that the guarantees in Theorem 2.8 are pseudo-approximations. That is, the approximation guarantee is with respect to the optimal set cover whereas the algorithm outputs a partial set cover.

3 An Application to Facility Location

To show an example where an explicit solution for (partial) set cover is a necessary building block for a larger algorithm, we will consider a facility location problem called MOBILEVACCCLINIC, introduced in [Li et al., 2022]. The authors introduced the following generalization of the well known ksupplier problem for deploying vaccine distribution sites:

Definition 3.1. Let C be a set of locations in a metric space with distance function d : C × C ↦→ R≥0. Let P be a set of n people where each person p ∈ P is associated with a set Sp ⊆ C, which can be interpreted as the set of locations p visits throughout the day. Finally, let k ∈ N be a budget on the number of facilities. We want to output a set of locations F ⊆ C with |F | ≤ k to place facilities which minimizes maxp∈P d(Sp, F), where d(S, F) = minj∈S,j ′∈F d(j, j ′ ). For simplicity, we normalize the metric so that the diameter is maxj,j ′∈C d(j, j ′ ) = 1.

We consider the outliers version of the above problem, where we are only required to serve ⌊ρn⌋ people in the population, for some ρ < 1. Since the problem was designed for vaccine distribution, the outliers variant is still very interesting: we only need to vaccinate 94% of the population in order to achieve herd immunity. For the differential privacy, the set of locations C, covering requirement ρ, and budget k is public information and the individuals along with their travel patterns is private information. We call two instances of MOBILEVACCCLINIC neighbors if they differ by exactly one individual p (along with their travel pattern Sp). Thus, we protect the privacy of the individuals: a differentially private algorithm's output will not differ too much whether or not any individual and their travel patterns are included in the data.

Unfortunately, we show that this problem is hard in a very strong sense: there cannot exist any (efficient or inefficient) algorithm which provides a finite approximation guarantee. Hence, we turn towards bicriteria algorithms where we violate the budget k: an algorithm is an (α, β)-bicriteria approximation for MOBILEVACCCLINIC with outliers if it obtains an additive β-approximation to the optimal radius while placing at most αk facilities. We show that this is possible. The idea of the algorithm is simple: we first guess the optimal radius R∗ via a binary search on the interpoint distances (in practice, we just guess R∗ up to an additive error of γ for faster convergence). Assuming we know R∗ , we consider the reverse problem where we wish to place the fewest facilities in order to cover a ρ fraction of the clients within a radius of R∗ . This is exactly a Partial Set Cover problem, so we can apply Algorithm 1 (it is easy to verify the privacy requirements of MOBILEVACCCLINIC matches that of Partial Set Cover). To formalize this, let the universe be U = P and let the set system be SR = {Sj(R) : j ∈ C}, where Sj(R) = {p ∈ P : d(Sp, j) ≤ R}. It is easy to see that this indeed reduces to a Partial Set Cover problem. In the following formalization of our algorithm, let α(ϵ, δ) denote the approximation guarantee of Algorithm 1:

Algorithm 3 DPCLIENTCOVER:

Input: MOBILEVACCCLINIC instance (C, S, P, k, ρ), ad-

ditive error γ, and privacy parameters (ϵ, δ) let ϵ′ ← ϵ/log2(1/γ), δ′ ← δ/log2(1/γ) let low ← 0, high ← 1 while high - low > γ do R ← (high + low)/2 Calculate SR as described above FR ← MPartialSetCover(C, SR, ρ, ϵ′ , δ′ ) if |FR| > α(ϵ′ , δ′ ) · k then low ←R otherwise high ← R end while Output FR for minimum R such that |FR| ≤ α(ϵ′ , δ′ ) · k.

Theorem 3.2. For any γ > 0, Algorithm 3 is (2ϵ, δ)-DP and an (O ( log2 |C| log(1/γ) log(1/δ) ϵ ) , γ)-approximation algorithm for MOBILEVACCCLINIC with outliers, with probability at least 1- ˜O ( 1 |C| ), when |C| = O(n).

Proof. The privacy guarantee is easy: since the guesses R don't depend on the private information, (2ϵ, δ)-differential privacy follows directly by basic composition. Note that we are allowed to find the minimum R such that |FR| ≤ α · k by post-processing, since the FR's are private already.

Next, we turn to the utility guarantee. Let us analyze the algorithm for the iterations of binary search where R ≥ R∗ . We will show that for these iterations, we necessarily have |FR| ≤ α(ϵ′ , δ′ ) · k. This implies that the binary search converges to some R satisfying R ≤ R∗ + γ, so the minimum R satisfying |FR| ≤ α(ϵ′ , δ′ ) · k also will satisfy R ≤ R∗ + γ.

To complete the proof, let's prove our claim. Suppose R ≥ R∗ and consider the corresponding Partial Set Cover instance. We know there exists some Partial Set Cover of size k (by the definition of R∗ ), so our approximation guarantees in Theorem 2.4 imply that |FR| ≤ α(ϵ′ , δ′ ) · k with probability 1 - O( 1n ). Apply the union bound over all iterations of the binary search completes the proof.

Remark 3. Our algorithm needs to violate the budget k by a poly-logarithmic multiplicative factor, which is often not possible in the real world. To circumvent this, we note that it has been observed experimentally that set cover algorithms obtain near optimal solutions; thus, we can implement Algorithm 3 with α set to 1 and still obtain a near-optimal radius R in practice. Even this contribution is non-trivial; before our work, even good heuristics were not known for differentially private k-supplier. We use this heuristic in the experiments in Section 4.

Remark 4. We state Algorithm 3 and its guarantees in terms of guessing the optimal radius R∗ up to an additive error of γ. We find that this converges faster in practice and thus obtains a better privacy/utility tradeoff. As mentioned before, binary searching on the interpoint distances can save us this additive error of γ but will lose a logarithmic factor in the number of facilities placed. The proof of this is very similar, and thus omitted.

3.1 Lower Bounds

To give our lower bound for MOBILEVACCCLINIC, we will first show that Partial Set Cover cannot be solved exactly under (ϵ, δ)-differential privacy and that an approximation is necessary (deferred to Appendix).

Lemma 3.3. Under (ϵ, δ)-differential privacy, Partial Set Cover cannot be solved exactly (with high probability).

We will use this fact to derive an information theoretic lower bound for MOBILEVACCCLINIC, stating that even computationally inefficient algorithms cannot give a finite approximation factor for this problem while simultaneously satisfying approximate differential privacy. Overall, this lower bound justifies our use of bicriteria approximation algorithms for our problem. The reduction we give is similar to the one found in [Anegg et al., 2022] for a separate problem, γcolorful k-center.

Theorem 3.4. There can be no finite approximation algorithm for MOBILEVACCCLINIC which satisfies (ϵ, δ)- differential privacy, even when the metric space is the Euclidean line.

Proof. Suppose for contradiction some differentially private approximation algorithm did exist with approximation ratio α = α(n, m, ρ, ϵ, δ). We will show that it can be used to solve any instance (U, S, ρ, ϵ, δ) of Differentially Private Partial Set Cover to optimality. By contradiction, we will conclude such an approximation algorithm cannot exist.

Let the metric space be the Euclidean line, let C = {1, . . . , |S|} and let the covering requirement be ρ = ρ. For each element uℓ ∈ U, define a person p ∈ P and let their travel locations be Sp = {i ∈ [|S|] : uℓ ∈ Si}. By construction, it is clear that the optimal solution for this MOBILEVACCCLINIC instance has radius 0 and gives a solution (of size k) to the Partial Set Cover instance. Furthermore, any α-approximation will output a solution with radius α · 0 = 0 as well. Consequently, we can binary search over k ∈ [m] to use any α-approximation for MOBILEVACCCLINIC to obtain an optimal solution for Partial Set Cover.

4 Experiments

For our experiments in our main paper, we focus on the vaccine distribution problem we studied in Section 3. We run all of our experiments on synthetic mobility data from Charlottesville city and Albemarle county, which are part of a synthetic U.S. population (see [Chen et al., 2021; Machi et al., 2021] for details). The data keeps track of the locations each person travels to throughout a week, so each person is associated with a set of activity locations. We use this data in our experiments to study the following:

• Privacy/Accuracy Tradeoff: how does the quality of our algorithm vary as the privacy parameters (ϵ, δ) vary?
• Cost of Privacy: how does our private algorithm compare with the non-private one given in [Li et al., 2022]?

Due to space constraints, we defer some of these experiments and analyses to the full version. There, we also investigate the above questions for our Partial Set Cover algorithms.

Baseline: We use a non-private greedy algorithm to solve the partial set cover problem as our Baseline. Starting with an empty set of locations, the greedy algorithm at each step chooses one location that covers the most of the uncovered clients. Then it adds the location to its set and updates the current state of covered clients. The baseline algorithm utilizes the same binary search routines with DPCLIENTCOVER to find the optimal radius.

Metric: All of our comparisons are made based on the objective value of MOBILEVACCCLINIC with outliers. Informally, by calculating the service cost of each person, our objective is to minimize the distance the ⌈ρn⌉th person needs to travel in order to get vaccinated. Formally, our objective is minP1⊆P:|P1|=⌈ρn⌉ maxp∈P1 d(Sp, F ).

4.1 Privacy/Accuracy/Budget Tradeoff

In this subsection, we investigate the two questions regarding the privacy/accuracy trade-off and the cost of privacy. We set δ = 10-6 and run our private vaccine distribution algorithm for different budgets k ∈ {4, . . . , 16} and different privacy parameters ϵ ∈ {0.25, 0.5, 1, 2, 4}. A careful reader may notice that Theorem 2.4 only applies for ϵ ∈ (0, 1), and may worry that our experimental regime doesn't have privacy guarantees. However, DPCLIENTCOVER makes calls to the Partial Set Cover algorithm with parameter ϵ′ = ϵ/ log2(1/γ), so we still have differential privacy.

The experimental results show that, generally, with higher values of budget, all algorithms perform better, i.e., they achieve lower objective values. Our private algorithm DPCLIENTCOVER usually achieves higher accuracy with higher ϵ at every level of budget, while the non-private algorithm (Baseline) always has the best performance. These results are expected. Figure 2 also shows that our private algorithm performs well, obtaining near optimal choices of facility locations for ϵ ≥ 1. For example, DPCLIENTCOVER with ϵ = 4 matches the performance of Baseline on the Albemarle dataset and almost matches the Baseline at several values of budget on the Charlottesville dataset. However, we can observe some trade-offs between privacy and utility, especially in high-privacy settings. In particular, for ϵ = 0.25 and k = 4, there is a high cost of guaranteeing privacy in both datasets. In these cases, the objectives of the private settings are 4-7 times higher than those of the Baseline.

A more subtle result that Figure 2 gives is to help us understand the trade-off between the budget and the privacy loss ϵ. From a policy-making perspective, this is interesting since we can allocate more mobile vaccine distribution sites in return for a stronger privacy guarantee. For example, the accuracy from k = 8 facilities with ϵ = 0.25 is similar to using k = 4 facilities with ϵ = 0.5. Figure 1 shows the vaccine clinics chosen by the private (ϵ = 0.5, white spots) and non-private (black spots) algorithms for the Charlottesville dataset with k = 8. The two algorithms tend to choose two totally different distributions of vaccine clinics, although they do not differ much in term of objective values (see Figure 2, where k = 8).

5 Discussion

In this paper, we consider the Set Cover problem and the ksupplier problem, which have strong hardness results under differential privacy. We observe that partial coverage of elements/clients suffices to avoid the impossibility results, and give the first non-trivial approximation algorithms for both problems. Overall, our work is an important step in tackling the impossibility results in differentially private algorithm design and leaves many interesting problems open:

• Both of our algorithms for Partial Set Cover require some (relatively loose) assumption on the set system. An interesting question is whether we can remove these assumptions: can we obtain a general approximation algorithm for Partial Set Cover under differential privacy?
• Our algorithm for k-supplier violates the budget k by a poly-logarithmic factor, which is impractical in some settings. It is interesting to see what guarantees are possible without violating the budget: can we obtain true approximations for k-supplier with outliers with privacy?
• As mentioned before, the facility location problem has a Ω(√n) approximation hardness result under differential privacy. It is interesting to see if our ideas can help avoid this: does allowing partial coverage circumvent hardness results of the uniform facility location problem?

Acknowledgements

Dung Nguyen and Anil Vullikanti were partially supported by NSF grants CCF 1918656, IIS 1955797, NIH grant 2R01GM109718-07, and CDC cooperative agreement MIND U01CK000589. George Li was supported in part by NSF award number CCF-1918749.