The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
Yi‐Jun Chang, Zeyong Li · 2023
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((log3(1/ϵ) log n) / ϵ) rounds.