Konstantin Makarychev: Algorithms for Semi-random instances of Unique Games and Graph Partitioning Problems

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 lecture, 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. I will also talk about semi-random Unique Games.

Based on joint works with Alexandra Kolla (UIUC), Yury Makarychev (TTIC), Aravindan Vijayaraghavan (Princeton).