The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
share
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 (ϵ, O(log n/ϵ)) low-diameter decomposition in O(log^3(1/ϵ)log n/ϵ) 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(log^3 (1/ϵ) log n/ϵ) rounds with probability 1 - 1/poly(n). For covering problems, our algorithm finds an (1+ϵ)-approximate solution in O((loglog n + log (1/ϵ))^3 log n/ϵ) rounds with probability 1 - 1/poly(n). These results improve upon the previous O(log^3 n/ϵ)-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±ϵ)-approximate solutions require Ω(log n/ϵ) rounds to compute.
READ FULL TEXT