[Colloquium] TTIC Talks: Aravindan Vijayaraghavan, Princeton

[Liv Leader]

*REMINDER:*

When:     Friday, February 10 @ 1 p.m.

Where:    TTIC, 6045 S. Kenwood Avenue, Room #526

Who:       Aravindan Vijayaraghavan, Princeton

Title:        Understanding Approximability through Average-case Analysis

I will talk about studying the average-case complexity of some fundamental
graph optimization problems
to better understand their approximability on both "real-world" instances
and worst-case instances.

In the first part, I will talk about algorithms for realistic models of
instances (not worst-case) of graph partitioning.
Graph partitioning problems are ubiquitous in computer science and form a
central topic of study, yet 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, I will 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, and also points to a concrete
barrier for further progress on Densest k-subgraph.

Host: Madhur Tulsiani, madhurt at ttic.edu

-- 
Liv Leader
Human Resources Coordinator

Toyota Technological Institute Chicago
6045 S Kenwood Ave
Chicago, IL 60637
Phone- (773) 702-5033
Fax-     (773) 834-9881
Email-  lleader at ttic.edu <jam at ttic.edu>
Web-   www.ttic.edu
<http://www.ttic.edu/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20120209/b03f9ef8/attachment.htm