Distributed Approximation of Maximum Independent Set and Maximum Matching
Distributed Approximation of Maximum Independent Set and Maximum Matching
复制标题
最大独立集和最大匹配的分布式逼近
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Gregory Schwartzman
中科院分区：
文献类型：
--
作者：
R. Bar;K. Censor;M. Ghaffari;Gregory Schwartzman
给出了拥塞模型中最大权独立集的一种简单的分布式Δ近似算法，该算法在O(M IS⋅LOG W)轮内完成，其中Δ是最大度，M IS是计算G上的最大独立集所需的轮数，W是节点的最大权.插入最著名的管理信息系统算法，可以在O(logn，logW)轮内得到随机解，其中n是节点数。给出了一种基于着色的确定性O(Δ+LOG*n)-轮算法。然后，我们展示了如何使用我们的Maxis近似算法来计算最大权重匹配的2-近似，而不会在拥塞模型中招致任何额外的轮次惩罚。我们使用已知的约简在导致拥塞的情况下对折线图上的算法进行仿真，但我们证明了我们的算法是一大类局部聚集算法的一部分，对于这些算法，我们描述了一种机制，允许模拟在拥塞模型中运行，而不会产生额外的开销。接下来，我们证明了对于最大权匹配，将近似因子放宽到(2+ε)允许我们设计一个分布式算法，对于任何常数Δ>；0都需要O((LOGΔ)/(LOGε))轮。对于未加权的情况，我们甚至可以在这个轮数内得到(1+ε)-近似。这些算法是第一个在依赖于Δ的情况下实现可证明的最优轮转复杂度的算法。
We present a simple distributed Δ-approximation algorithm for maximum weight independent set (MaxIS) in the CONGEST model which completes in O(MIS ⋅ log W) rounds, where Δ is the maximum degree, MIS is the number of rounds needed to compute a maximal independent set (MIS) on G, and W is the maximum weight of a node. Plugging in the best known algorithm for MIS gives a randomized solution in O(log n log W) rounds, where n is the number of nodes. We also present a deterministic O(Δ +log* n)-round algorithm based on coloring. We then show how to use our MaxIS approximation algorithms to compute a 2-approximation for maximum weight matching without incurring any additional round penalty in the CONGEST model. We use a known reduction for simulating algorithms on the line graph while incurring congestion, but we show our algorithm is part of a broad family of local aggregation algorithms for which we describe a mechanism that allows the simulation to run in the CONGEST model without an additional overhead. Next, we show that for maximum weight matching, relaxing the approximation factor to (2+ε) allows us to devise a distributed algorithm requiring O((log Δ)/(log logΔ)) rounds for any constant ε>0. For the unweighted case, we can even obtain a (1+ε)-approximation in this number of rounds. These algorithms are the first to achieve the provably optimal round complexity with respect to dependency on Δ.