Title: Approximation Algorithms for Semi-random Graph Partitioning Problems
Speaker: Aravindan Vijayaraghanvan, Princeton and CMU
Date: Monday, October 8, 2012 11:00am - 12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Graph partitioning problems are ubiquitous in computer science and form a central topic of study. However, constant factor approximations have been elusive. Since real-world instances are unlikely to behave like worst-case instances, a compelling question is: can we design better algorithms for realistic average case instances? We propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of realworld instances. The model is more flexible than the semi-random model of Feige and Kilian and the planted random model of Bui, Chaudhuri, Leighton and Sipser.
We develop a general framework for solving semi-random instances and apply it to several problems of interest. We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut and Small-Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than algorithms for previously studied random and semi-random models.
This is based on joint work with Konstantin Makarychev and Yury Makarychev.
DIMACS/CCICADA Interdisciplinary Series, Complete Fall Calendar 2012