Differentially Private Partial Set Cover with Applications to Facility Location
Differentially Private Partial Set Cover with Applications to Facility Location
复制标题
DOI：
10.48550/arxiv.2207.10240
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
George Z. Li;Dung Nguyen;A. Vullikanti
中科院分区：
文献类型：
--
作者：
George Z. Li;Dung Nguyen;A. Vullikanti
集合覆盖问题是组合优化中的一个基本问题，由于其在多个领域的广泛应用，已经被研究了几十年。在这些域中的许多域中，输入数据由可能由于集合覆盖输出而泄露的个体的位置、关系和其他敏感信息组成。已经尝试设计隐私保护算法来解决隐私约束下的集合覆盖。在差分隐私下，集合覆盖问题具有强不可能性结果，并且没有明确的输出形式可以向公众发布。在这项工作中，我们观察到，当我们转向部分集合覆盖问题时，这些硬度结果消失了，在那里我们只需要覆盖元素的ρ ∈（0，1）部分。我们表明，这种放松使我们能够避免不可能的结果，并给出了第一个算法，输出一个明确的形式的集覆盖与非平凡的效用保证下的差分隐私。使用我们的算法作为一个子程序，我们设计了一个差分私有双准则算法来解决最近提出的设施定位问题的疫苗分配，推广了k-供应商与离群值。我们的分析表明，放宽覆盖要求，只服务于人口/宇宙的一个ρ ∈（0，1）部分，也允许我们绕过k-供应商的固有硬度，并给出第一个非平凡的保证。
Set Cover is a fundamental problem in combinatorial optimization which has been studied for many decades due to its various applications across multiple domains. In many of these domains, the input data consists of locations, relationships, and other sensitive information of individuals which may leaked due to the set cover output. Attempts have been made to design privacy-preserving algorithms to solve the Set Cover under privacy constraints. Under differential privacy, it has been proved that the Set Cover problem has strong impossibility results and no explicit forms of the output can be released to the public. In this work, we observe that these hardness results dissolve when we turn to the Partial Set Cover problem, where we only need to cover a ρ ∈ (0,1) fraction of the elements. We show that this relaxation enables us to avoid the impossibility results, and give the first algorithm which outputs an explicit form of set cover with non-trivial utility guarantees under differential privacy. Using our algorithm as a subroutine, we design a differentially private bicriteria algorithm to solve a recently proposed facility location problem for vaccine distribution which generalizes the k-supplier with outliers. Our analysis shows that relaxing the covering requirement to serve only a ρ ∈ (0,1) fraction of the population/universe also allows us to circumvent the inherent hardness of k-supplier and give the first non-trivial guarantees.