Approximation algorithms for semi-random partitioning problems
Konstantin Makarychev, Yury Makarychev, Aravindan Vijayaraghavan · 2012
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.