# Differentially Private Partial Set Cover with Applications to Facility Location

arXiv: https://arxiv.org/abs/2207.10240 · HTML: https://mlsanity.com/paper/2207.10240/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 21 Jul 2022.

## Builds on (most cited first, 13 of 13)

- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget](https://mlsanity.com/paper/1808.09501/) (2018)
- [Private Identity Testing for High-Dimensional Distributions](https://mlsanity.com/paper/1905.11947/) (2019)
- [A Technique for Obtaining True Approximations for k-Center with Covering Constraints](https://mlsanity.com/paper/2007.03946/) (2020)
- [Scalable Differentially Private Clustering via Hierarchically Separated Trees](https://mlsanity.com/paper/2206.08646/) (2022)
- [Differentially Private Clustering via Maximum Coverage](https://mlsanity.com/paper/2008.12388/) (2020)
- [Privately Solving Linear Programs](https://mlsanity.com/paper/1402.3631/) (2014)
- [Differentially Private Densest Subgraph Detection](https://mlsanity.com/paper/2105.13287/) (2021)
- [Differentially-Private Sublinear-Time Clustering](https://mlsanity.com/paper/2112.13751/) (2021)
- [Facility Location Problem in Differential Privacy Model Revisited](https://mlsanity.com/paper/1910.12050/) (2019)
- [Deploying Vaccine Distribution Sites for Improved Accessibility and Equity to Support Pandemic Response](https://mlsanity.com/paper/2202.04705/) (2022)

## Built on by (most cited first, 1 of 1)

- [Improving Epidemic Analyses with Privacy-Preserving Integration of Sensitive Data](https://mlsanity.com/paper/2506.22342/) (2025)

## Abstract (arXiv)

It was observed in citetgupta2009differentially that the Set Cover problem has strong impossibility results under differential privacy. In our work, we observe that these hardness results dissolve when we turn to the Partial Set Cover problem, where we only need to cover a ρ-fraction of the elements in the universe, for some ρ∈(0,1). We show that this relaxation enables us to avoid the impossibility results: under loose conditions on the input set system, we give differentially private algorithms which output an explicit set cover with non-trivial approximation guarantees. In particular, this is the first differentially private algorithm which outputs an explicit set cover. Using our algorithm for Partial Set Cover as a subroutine, we give a differentially private (bicriteria) approximation algorithm for a facility location problem which generalizes k-center/k-supplier with outliers. Like with the Set Cover problem, no algorithm has been able to give non-trivial guarantees for k-center/k-supplier-type facility location problems due to the high sensitivity and impossibility results. Our algorithm shows that relaxing the covering requirement to serving only a ρ-fraction of the population, for ρ∈(0,1), enables us to circumvent the inherent hardness. Overall, our work is an important step in tackling and understanding impossibility results in private combinatorial optimization.