Many combinatorial optimization problems are much simpler in practice than in the worst-case. One of the challenges in the area of approximation algorithms is to explain this phenomenon and to design algorithms that work well in real-life. In this talk, we will discuss one of the models of real-life instances -- the semi-random model, which was originally introduced by Blum and Spencer for the k coloring problem. I will describe a new semi-random model for graph partitioning problems and present a constant factor approximation algorithm for semi-random instances of Balanced Cut. I will also mention our results for semi-random instances of other combinatorial optimization problems.

Joint work with Konstantin Makarychev (Microsoft Research) and Aravindan Vijayaraghavan (Princeton and CMU)