The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs

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.