Differentially Private Partial Set Cover with Applications to Facility Location
This work addresses the problem of designing differentially private algorithms for combinatorial optimization tasks, which is significant for privacy-preserving data analysis, though it is incremental as it builds on known hardness results by introducing a relaxation.
The paper tackles the challenge of differential privacy in combinatorial optimization by focusing on the Partial Set Cover problem, where only a fraction of elements need to be covered, and shows that this relaxation allows for differentially private algorithms with non-trivial approximation guarantees, including the first such algorithm for explicit set cover. It applies this to facility location problems like k-center with outliers, demonstrating that relaxing coverage requirements circumvents previous impossibility results.
It was observed in \citet{gupta2009differentially} 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 $ρ\in(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 $ρ\in(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.