Simple and Local Independent Set Approximation
Simple and Local Independent Set Approximation
复制标题
简单局部独立集逼近
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Dror Rawitz
中科院分区：
文献类型：
--
作者：
R. Boppana;M. Halldórsson;Dror Rawitz
我们给出了有界度图中未加权独立集和加权独立集的类似图安界所得到的性能保证。特别是，Boppana的随机化方法形成了简单的1轮分布式算法，以及流和抢占式在线算法。我们证明了它在最大度为$Delta$的未加权图中给出了一个紧的$(Delta+1)/2$-逼近，这对于1轮分布式算法是最可能的。对于加权图，它只给出一个$Delta$-近似，但简单的修改就会得到一个渐近预期的$0.529 Delta$-近似。这与最近更复杂的$Delta$-近似~Cite{BCGS17}形成了鲜明的对比。
We bound the performance guarantees that follow from Tur'an-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 $(Delta+1)/2$-approximation in unweighted graphs of maximum degree $Delta$, which is best possible for 1-round distributed algorithms. For weighted graphs, it gives only a $Delta$-approximation, but a simple modification results in an asymptotic expected $0.529 Delta$-approximation. This compares with a recent, more complex $Delta$-approximation~cite{BCGS17}, which holds deterministically.
DOI：
--
发表时间：
2017-02
期刊：
ArXiv
影响因子：
--
作者：
Graham Cormode;J. Dark;C. Konrad
通讯作者：
Graham Cormode;J. Dark;C. Konrad