[Colloquium] Guest Speaker

[Ponda Barnes]

Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Nikhil Devanur
Speaker's homepage: www.cc.gatech.edu/~nikhil
 
Date: Thursday, April 05, 2007
Time: 10:00
Location: TTI-C Conference room
 
Title: Two results in approximation algorithms
 
Abstract:
I will talk about two fundamental problems in approximation  algorithms, and
present a positive result for one and a negative result for the other.
 
The balanced separator problem is to cut a given graph into two pieces of
linear size so that the number of edges crossing the cut is minimized; it is
widely used as a subroutine in many
divide-and-conquer algorithms, in applications to VLSI layout, clustering
and parallel computing, and in the theory of Markov chains and metric
embeddings.  In a breakthrough result, Arora, Rao and
Vazirani gave an O(\sqrt{\log n }) factor approximation algorithm for this
problem, based on a semi-definite programming (SDP) relaxation.  It was
actually conjectured that this approach could lead to a
constant factor approximation. I will present an Omega(\log\log n) lower
bound on the integrality gap of  this SDP relaxation, that  disproves this
conjecture.
 
The Steiner tree problem is to design a network of minimum cost that
connects all the "required" vertices and any of the "Steiner" vertices, in a
given graph with edge costs.  This problem is a natural
generalization of the minimum spanning tree problem and has numerous
applications in network design, VLSI design, phylogenetic tree
reconstruction, etc.  A long standing open problem is to determine the
integrality gap of the bi-directed cut relaxation for this problem and to
exploit it algorithmically. I will show a new geometric relaxation for this
problem which turns out to be exactly equivalent to the
bi-directed cut relaxation, and helps us obtain a 4/3 factor algorithm and
integrality gap bound for the case of quasi-bipartite graphs; the previous
best being 3/2.  This is based on joint work with [Subhash Khot, Rishi Saket
and Nisheeth Vishnoi] and with [Deeparnab Chakrabarti and Vijay Vazirani].
 
If you have any questions  or would like to meet the speaker, please contact
Ponda Barnes at pondabarnes at tti-c.org
For future TTI-C talks and events please go to
http://ttic.uchicago.edu/cal/month.php
 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20070405/cf96d0a2/attachment.htm