


























In this paper, we present a low-diameter decomposition algorithm in the LOCAL model of distributed computing that succeeds with probability $1 - 1/poly(n)$. Specifically, we show how to compute an $\left(ε, O\left(\frac{\log n}ε\right)\right)$ low-diameter decomposition in $O\left(\frac{\log^3(1/ε)\log n}ε\right)$ round Further developing our techniques, we show new distributed algorithms for approximating general packing and covering integer linear programs in the LOCAL model. For packing problems, our algorithm finds an $(1-ε)$-approximate solution in $O\left(\frac{\log^3 (1/ε) \log n}ε\right)$ rounds with probability $1 - 1/poly(n)$. For covering problems, our algorithm finds an $(1+ε)$-approximate solution in $O\left(\frac{\left(\log \log n + \log (1/ε)\right)^3 \log n}ε\right)$ rounds with probability $1 - 1/poly(n)$. These results improve upon the previous $O\left(\frac{\log^3 n}ε\right)$-round algorithm by Ghaffari, Kuhn, and Maus [STOC 2017] which is based on network decompositions. Our algorithms are near-optimal for many fundamental combinatorial graph optimization problems in the LOCAL model, such as minimum vertex cover and minimum dominating set, as their $(1\pm ε)$-approximate solutions require $Ω\left(\frac{\log n}ε\right)$ rounds to compute.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。