Approximation algorithms for semi-random partitioning problems

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.

Authors

• Konstantin Makarychev
• Yury Makarychev
• Aravindan Vijayaraghavan

Keywords

• random planted model
• semi-random model
• average-case analysis
• graph partitioning
• approximation algorithm