Approximating Independent Sets in Constant Distributed Rounds
摘要
A simple randomized one-round distributed algorithm for approximating independent sets in graphs was studied by Boppana, Halldorsson, and Rawitz (SIROCCO 2018). It was shown to attain a \((\varDelta +1)/2\) -approximation on unweighted graphs of maximum degree \(\varDelta \) , but only in expectation. We show here that the same bound holds with high probability, with minimal loss. This means that the algorithm is optimal in the class of 1-round algorithms. It is also better by a factor of \(2-o(1)\) than all known \(o(\log n)\) -round algorithms. For graphs of constant degree, the algorithm can be derandomized in \(O(\log ^* n)\) rounds.