削减不平衡图 - Sci-Hub|Scidown

Scidown文献预览系统！

作者：scidown 发布时间：2021-08-03 16:26:08 文章标题：

削减不平衡图( Unbalanced Graph Cuts )

文章作者：

A Hayrapetyan D Kempe M Pál Z Svitkina CiteSeerX Ara Hayrapetyan David Kempe Martin Pál Zoya Svitkina

文章简述：

本文引入了最小尺寸有界容量割(MinSBCC)问题，给出了一个具有已知源的图，在其容量不超过规定界B的条件下，寻求一个使源侧节点数最小的割。除了对图割的研究感兴趣之外，这个问题还存在于许多实际应用中，如流行病学、灾害控制、军事控制以及图中稠密子图和图中稠密群的寻找等。一般情况下，MinSBCC问题是NP完全的。对于任意0<λ<1,我们给出了一个有效的((frac{1}{{mlambda}},frac{1}{1-{mlambda}}）-bicriteria近似算法；也就是说，该算法最多找到一个截断的容量(frac{1}{{mlambda}}b)，最多在源端留下(frac{1}{1-{mlambda}}})倍于容量B的最优解的顶点。事实上，该算法的解决方案要么违反预算约束，要么超过源端节点的最优数量，但不是两者兼而有之。对于树宽有界的图，我们证明了具有单位权节点的问题可以在多项式时间内得到最优解，当节点有权时，可以用PTAS任意逼近。

文章下载地址（开放版）：