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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Approximating Independent Sets in Constant Distributed Rounds

  • Ravi B. Boppana,
  • Magnús M. Halldórsson

摘要

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.