Approximation Algorithms for Semi-random Graph Partitioning Problems
Approximation Algorithms for Semi-random Graph Partitioning Problems
复制标题
半随机图划分问题的近似算法
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
Aravindan Vijayaraghavan
中科院分区：
文献类型：
--
作者：
K. Makarychev;Yury Makarychev;Aravindan Vijayaraghavan
在本文中，我们提出并研究了用于图形分配问题的新的半随机模型。我们认为，它捕获了真实世界实例的许多属性。该模型比Feige和Kilian的半随机模型更灵活，以及Bui，Chaudhuri，Leighton和Sipser的随机模型。
我们开发了一个通用框架来解决半随机实例，并将其应用于一些感兴趣的问题。我们介绍了平衡切割，多功能，最小未切割，最稀疏的剪切和小设置膨胀问题的半随机实例的恒定因子双重标准近似算法。如果实例满足额外的扩展条件，我们还展示了如何几乎几乎恢复最佳解决方案。与以前研究的随机和半随机模型相比，我们的算法在更广泛的参数范围内起作用。
此外，我们研究了一个新的种植的代数扩展器模型，并开发了该模型中图形分配问题的恒定因子双标准近似算法。
In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real--world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser.
We develop a general framework for solving semi-random instances and apply it to several problems of interest. We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut, Sparsest Cut and Small Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than most algorithms for previously studied random and semi-random models.
Additionally, we study a new planted algebraic expander model and develop constant factor bi-criteria approximation algorithms for graph partitioning problems in this model.