
























We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in a hypergraph of rank $r$. Our main result is a deterministic algorithm to generate a matching which is an $O(r)$-approximation to the maximum weight matching, running in $\tilde O(r \log Δ+ \log^2 Δ+ \log^* n)$ rounds. (Here, the $\tilde O()$ notations hides $\text{polyloglog } Δ$ and $\text{polylog } r$ factors). This is based on a number of new derandomization techniques extending methods of Ghaffari, Harris & Kuhn (2017). As a main application, we obtain nearly-optimal algorithms for the long-studied problem of maximum-weight graph matching. Specifically, we get a $(1+ε)$ approximation algorithm using $\tilde O(\log Δ/ ε^3 + \text{polylog}(1/ε, \log \log n))$ randomized time and $\tilde O(\log^2 Δ/ ε^4 + \log^*n / ε)$ deterministic time. The second application is a faster algorithm for hypergraph maximal matching, a versatile subroutine introduced in Ghaffari et al. (2017) for a variety of local graph algorithms. This gives an algorithm for $(2 Δ- 1)$-edge-list coloring in $\tilde O(\log^2 Δ\log n)$ rounds deterministically or $\tilde O( (\log \log n)^3 )$ rounds randomly. Another consequence (with additional optimizations) is an algorithm which generates an edge-orientation with out-degree at most $\lceil (1+ε) λ\rceil$ for a graph of arboricity $λ$; for fixed $ε$ this runs in $\tilde O(\log^6 n)$ rounds deterministically or $\tilde O(\log^3 n )$ rounds randomly.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。