MPC模型中的快速集合覆盖

《Theoretical Computer Science》：Faster Set Cover in the MPC Model

　　

•提出了在MPC模型中求解集合覆盖问题的首个O(logn)近似算法，该算法在具有n个元素和m个集合的实例上运行o(log2(m + n))轮。•提出了在低内存MPC模型中实现?(log1·?N)轮的算法。•提出了在线性内存MPC模型中运行?(logN)轮的算法。•重新利用了来自最大独立集问题的稀疏化图幂运算技术，并用一种新的元素采样方法对其进行扩展。

引言
我们提出了在大规模并行计算（MPC）模型中求解集合覆盖问题的快速算法。在集合覆盖问题中，给定一个包含n个元素的基础集和一个由m个集合组成的集合族，它们共同覆盖所有元素。目标是找到仍能覆盖所有元素的最小子集合。集合覆盖是一个经典的组合优化问题，是许多已广泛研究问题的推广，如顶点覆盖、边覆盖和最小支配集。MPC模型由一组通过全互联通信网络连接的机器M定义，每台机器具有最多W个字的本地内存（一个字为O(log N)位，其中N=n+m）。在此模型中，通信和计算是同步进行的。在算法开始时，输入分布在机器之间。在一轮中，每台机器接收来自其他所有机器的最多W个字，执行本地计算，并向其他所有机器发送最多W个字以指导下一轮的计算。请注意，在此模型中，带宽约束与单个边无关，而是与每台机器相关联。

一个自然、贪心的串行算法可给出lnn+O(1)近似。这基本上是最优的，因为对于任何c < 1，除非P=NP，否则不可能存在c ln n的集合覆盖近似算法。集合覆盖问题在并行设置中也得到了广泛研究，已知存在O(log n)近似算法，这些算法作为分布式集合覆盖近似算法的基础。例如，在分布式计算的Congest模型中，Censor-Hillel和Dory的工作意味着存在一个保证O(log n)近似比的集合覆盖问题算法，需要O(log2N)轮，其中N=n+m。该Congest算法以高概率（即概率至少为1?1/Nc，其中c ≥ 1为常数）成功。

存在一个活跃的研究流，旨在为各种问题设计比其Congest对应物显著更快的MPC算法。特别是，对于最大独立集（MIS）问题，Congest模型中的最快算法是一个随机算法，其轮复杂度（以顶点数N表示）为O(log N)，而在低内存MPC模型中为?(logN)，在线性内存MPC模型中为O(log log N)。但是，据我们所知，集合覆盖似乎至今一直抵抗这种改进，已知的最快MPC算法只是逐轮模拟最快的Congest算法，需要O(log2N)轮。在这篇论文中，受MIS获得的速度提升启发，我们证明了存在显著更快的集合覆盖MPC算法。具体来说，我们证明了以下定理。

定理 [非正式主要结果] 给定一个具有n个元素的基础集和m个集合的集合覆盖实例。令N=m+n。我们可以以高概率计算一个O(log n)近似的集合覆盖解，该解在以下情况中运行：
•在低内存MPC模型中运行?(log1·?N)轮
•在线性内存MPC模型中运行?(logN)轮

集合覆盖问题的输入是基础集X，|X|=n，以及满足∪?S?=X的子集集合S={S?,S?,…,S?}。问题要求输出最小的子集合C?S，使得∪_{S∈C}S=X。对于集合覆盖实例，我们用s表示最大集合的大小，用t表示一个元素出现的最大集合数。集合覆盖实例可以表示为二部图G=(X,S,E)，节点集X∪S的大小为N=m+n，边集E由边{S, x}组成，其中x ∈ X，S∈S，且x ∈ S。

在MPC模型中，每台机器的本地内存W和使用的机器数|M|都被假设为输入大小I的次线性函数。具体来说，W=I^α且|M|=I^β，其中0 < α < 1和0 < β < 1为常数。假设机器数|M|足够大，以便我们有足够的内存存储整个输入，即|M|·W≥I。

当输入是N节点图时，设计MPC算法的困难似乎与每台机器的内存W如何与N相关联有关。出于这个原因，研究人员分别研究了以下三种内存大小制度。请注意，在所有三种制度中，我们仍然需要确保本地内存参数W是总输入大小I的次线性函数。请注意，I可以大到m·n。

低内存MPC：每台机器W=Θ(N^δ)内存，0 < δ < 1。
线性内存MPC：每台机器W=Θ(N)内存。
超线性内存MPC：每台机器W=Θ(N^{1+δ})内存，0 < δ < 1。

已知集合覆盖可以在超线性内存MPC模型中以O(1)轮近似求解（详见下文第3节）。我们的论文关注两个更具挑战性的内存制度：低内存MPC和线性内存MPC。

在MPC模型中，标准假设是输入图的边在机器间任意分布。但假设输入以以节点为中心的方式分布来设计算法更方便。也就是说，对于输入图中的每个节点v，有一台机器Mv托管它，Mv知道v的所有邻居以及托管这些邻居的机器。只要不违反本地内存约束，一台机器可以托管多个顶点。

在低内存MPC模型中立即出现的问题是，一个节点的度数本身可能太大，无法适应一台机器。我们以标准方式解决这个问题。我们首先用一棵深度为O(1/δ)的虚拟N^{O(δ)}叉平衡树替换节点v（deg(v)>N^δ）的关联边。这棵树的根是v，叶子是v的邻居。每个中间节点是度数为N^{O(δ)}的虚拟节点，因此每个虚拟节点的邻居都可以适应一台机器。通过这棵树在v及其邻居之间的通信需要O(1/δ)轮，而不是仅仅1轮。

技术贡献
我们的起点是Grunau、Mitrovi?、Rubinfeld和Vakilian提出的简单集合覆盖算法。对于我们而言，最好将其视为分布式Congest模型算法。在下面的伪代码（算法1）中，s是S中最大集合的大小，t是元素出现的最大集合数。我们用degi,k(S)表示在第i阶段第k次迭代开始前S中未覆盖元素的数量。该算法在期望上产生O(log s)近似解。

相关工作
Harvey、Liaw和Liu提出了可以视为O(1)轮超线性内存MPC算法的内容，为加权集合覆盖提供了t近似算法。更准确地说，在具有n^{1+c}条边的图上，他们的算法运行O((c/μ)2)轮，其中假设每台机器的空间为Θ(t·n^{1+μ})。

还值得一提的是，Grunau、Mitrovi?、Rubinfeld和Vakilian使用他们的基算法设计本地计算算法（LCA）模型中的算法，具有小查询复杂度。

低内存MPC算法
固定任意阶段i。该阶段中的log t次迭代被划分为批次，每个批次由δlogN/4次迭代组成。更准确地说，令P?=δlogN/4·(j?1)表示批次边界。然后批次j（j=1,2,…）包含迭代P?+1到P?+δlogN/4。回顾一下，如果degi,P?+1(S)≥s/2?，则集合S被称为批次j的候选集。每个候选集S为P?+1≤k≤P?+δlogN/4抛掷δlogN/4枚硬币c?(S)，Prob[c?(S)=1]=2?/t，以模拟候选集的随机选择。

线性内存MPC中的指数级加速模拟
在本节中，我们将展示在线性内存MPC模型中，上一节的模拟可以大大简化并加速，导致一个以高概率运行O(log s · log log N)轮的算法。我们的主要见解是，阶段中大量初始迭代引起的活动图的大小为O(N)。这意味着这些初始迭代可以在常数轮内在线性内存MPC模型中模拟。

特别是，对于任何阶段i，考虑迭代……

结论与未来工作
这篇论文提出了经典集合覆盖问题在线性内存和低内存MPC模型中分别为首个?(logN)轮和?(log1·?N)轮算法。我们注意到，Dhulipala、Dinitz、?a?cki和Mitrovi?独立地在同一时间获得了相同的结果。这些算法是使用稀疏化图幂运算技术获得的，该技术此前用于为最大独立集和2-支配集获得更快的MPC算法，并与……相结合。

CRediT作者贡献声明
Hongyan Ji：写作 - 审阅与编辑，写作 - 原稿。Shreyas Pai：写作 - 审阅与编辑，写作 - 原稿。Sriram V. Pemmaraju：写作 - 审阅与编辑，写作 - 原稿。Joshua Sobel：写作 - 审阅与编辑，写作 - 原稿。

利益冲突声明
作者声明他们没有已知的竞争财务利益或个人关系，这些利益或关系可能影响本论文中报告的工作。

Hongyan Ji | Shreyas Pai | Sriram V. Pemmaraju | Joshua Sobel