论文标题
在超图中匹配的分布式算法
Distributed Algorithms for Matching in Hypergraphs
论文作者
论文摘要
$ $我们研究$ d $均匀的超盖匹配（$ d $ -uhm）问题：给定一个$ n $ vertex hypergraph $ g $，每个hyperege均为尺寸$ d $，找到最大的Disbinatity Dissinational discoint Hyperedges。对于$ d \ geq3 $，查找最大匹配的问题是NP完整的，并且是KARP的21 $ \ Mathcal {np} $ - 完整问题之一。在本文中，我们对在大量平行计算（MPC）模型中找到匹配的问题感兴趣，该模型是MapReduce式计算的常见抽象。在此模型中，我们以$ d $均匀的超图匹配介绍了前三种并行算法，并根据资源（例如内存使用情况，所需的通信回合和近似值）进行分析。亮点包括： $ \ bullet $ a $ o（\ log n）$ - 回合$ d $ - Approximation算法，使用$ O（nd）$每台机器。 $ \ bullet $ a $ 3 $ -ROUND，$ o（d^2）$ - 使用$ \ tilde {o}（\ sqrt {nm}）$ space每台机器的近似算法。 $ \ bullet $ a $ 3 $ -ROUND算法计算包含$（d-1+\ frac {1} {1} {d}）^2 $ -approximation的子图，使用$ \ tilde {o}（o \ tilde {o}（\ sqrt {nm}） $ \ tilde {o}（n \ sqrt {nm}）一般。
$ $We study the $d$-Uniform Hypergraph Matching ($d$-UHM) problem: given an $n$-vertex hypergraph $G$ where every hyperedge is of size $d$, find a maximum cardinality set of disjoint hyperedges. For $d\geq3$, the problem of finding the maximum matching is NP-complete, and was one of Karp's 21 $\mathcal{NP}$-complete problems. In this paper we are interested in the problem of finding matchings in hypergraphs in the massively parallel computation (MPC) model that is a common abstraction of MapReduce-style computation. In this model, we present the first three parallel algorithms for $d$-Uniform Hypergraph Matching, and we analyse them in terms of resources such as memory usage, rounds of communication needed, and approximation ratio. The highlights include: $\bullet$ A $O(\log n)$-round $d$-approximation algorithm that uses $O(nd)$ space per machine. $\bullet$ A $3$-round, $O(d^2)$-approximation algorithm that uses $\tilde{O}(\sqrt{nm})$ space per machine. $\bullet$ A $3$-round algorithm that computes a subgraph containing a $(d-1+\frac{1}{d})^2$-approximation, using $\tilde{O}(\sqrt{nm})$ space per machine for linear hypergraphs, and $\tilde{O}(n\sqrt{nm})$ in general.
