2018/03/02 by Boppana, Ravi B., Halldórsson, Magnús M., Rawitz, Dror · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1803.00786
We bound the performance guarantees that follow from Turán-like bounds for unweighted and weighted independent sets in bounded-degree graphs. In particular, a randomized approach of Boppana forms a simple 1-round distributed algorithm, as well as a streaming and preemptive online algorithm. We show it gives a tight (Δ+1)/2-approximation in unweighted graphs of maximum degree Δ, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a Δ-approximation, but a simple modification results in an asymptotic expected 0.529 Δ-approximation. This compares with a recent, more complex Δ-approximation~\citeBCGS17, which holds deterministically.