Show icon Show search tips...
Hide icon Hide search tips...

[CCICADA-announce] DIMACS/CCICADA Interdisciplinary SeminarSeries - Monday, October 8, 2012

Linda Casals lindac at
Wed Oct 3 14:06:44 EDT 2012


DIMACS/CCICADA Interdisciplinary Seminar Series Presents

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

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

DIMACS/CCICADA Interdisciplinary Series, Fall Calendar 2012-

More information about the Dimacs-ccicada-announce mailing list