Title: Algorithms for Semi-random Graph Partitioning Problems

Abstract: 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 present a new semi-random model for graph partitioning
problems and give a constant factor approximation algorithm for
semi-random instances of Balanced Cut.

Joint work with Yury Makarychev (TTIC) and Aravindan Vijayaraghavan
(Princeton)