Аспирантский семинар: Beyond Worst Case Analysis of Graph Partitioning Algorithms
Докладчик: Константин Макарычев (Microsoft Research)
Место: Факультет компьютерных наук, Кочновский проезд, д. 3, ауд. 317
Время: 21 мая, 18:30 – 20:00
Доклад состоится в рамках совместного заседания научно-исследовательского семинара аспирантской школы по компьютерным наукам и коллоквиума факультета компьютерных наук.
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 first discuss different ways of modelling “real-life” instances. Then, I will present a new semi-random semi-adversarial model for graph partitioning problems, a planted model with permutation-invariant random edges (PIE). This model is much more general than stochastic models considered previously. Finally, I will describe a “constant factor” approximation algorithm for finding the minimum balanced cut in graphs from this model.
This is a joint work with Yury Makarychev and Aravindan Vijayaraghavan.