[talks] A Vijayaraghavan preFPO

Melissa M. Lawson mml at CS.Princeton.EDU
Thu Mar 1 14:32:14 EST 2012

Aravindan Vijayaraghavan will present his preFPO on 
Wednesday March 7 at 11AM in Room 302 (note room).  The 
members of his committee are:  Moses Charikar, advisor; 
Sanjeev Arora and Mark Braverman, readers; David Blei 
and Konstantin Makarychev, nonreaders.  Everyone is invited
to attend his talk.  His abstract follows below.

Understanding Approximability through Average-case Analysis

We study the approximability of fundamental graph optimization problems through
approximation algorithms for both realistic average-case and
worst-case instances of problems.
We study average-case instances to shed new light on approximability
in two ways :
1. designing better algorithms for realistic average-case instances.
2. designing new algorithms with better guarantees even in worst-case, and
    identifying new barriers for further progress.

In the first part of the thesis, we study Graph partitioning problems
which 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 study a semi-random model for graph partitioning problems, that is
more general than previously studied random models, and that seems to 
capture many real-world instances well. We design new O(1) approximation 
algorithms for classical graph partitioning problems like Balanced Separator,
Sparsest cut, Multicut and Small set expansion for these semi-random
instances. Our algorithms are based on new SDP-based techniques and
work in a wider range of parameters than algorithms for previously
studied random and semi-random models.

In the second part, we show how insights from algorithms for a natural
average-case version are used to obtain new worst-case approximation 
algorithms for the Densest k-Subgraph problem -- an important yet poorly 
understood problem in combinatorial optimization. The counting-based algorithms 
for the average-case version of the problem are translated to algorithms for 
the worst-case using linear programming hierarchies: this gives
an improved n^{1/4} factor approximation. Studying the average-case
version also points to a concrete barrier for further progress on
approximations for Densest k-subgraph.

These results are based on joint works with Aditya Bhaskara, Moses
Charikar, Eden Chlamtac, Uriel Feige, Venkatesan Guruswami, Konstantin
Makarychev, Yury Makarychev and Yuan Zhou.

More information about the talks mailing list