[Colloquium] Guest Speaker Announcement

[Ponda Barnes]

TTI-C Guest Speaker
 
Presented by: Toyota Technological Institute at Chicago
 
Speaker: Sanjeev Khannna
Speaker's home page: http://www.cis.upenn.edu/~sanjeev/
 
Date: Tuesday, October 9, 2007
Time: 11:00
Location: TTI-C Conference room, 2nd floor
 
 
Title: Disjoint Paths in Networks
 
Abstract:
A fundamental problem in combinatorial optimization is the edge-disjoint
paths problem (EDP).  We are given a network and a collection of
source-destination pairs in the network.
The goal is to maximize the number of pairs that can be connected by
edge-disjoint paths.  Even special cases of EDP correspond to non-trivial
optimization problems, and the problem becomes NP-hard in very restricted
settings.
 
In this talk, we will survey some recent progress on understanding the
approximability threshold of EDP and its variants. While the recent
developments have essentially resolved the approximability of EDP and
related problems in directed graphs, the status of the undirected case
remains wide open.  We will describe a promising framework for getting
much-improved algorithms for undirected EDP when some congestion is allowed.
In particular, we will highlight a conjecture whose resolution is strongly
tied to the approximability of the undirected case, and describe some
results that lend support to this conjecture.
 
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 events please visit http://ttic.uchicago.edu/cal/month.php
. (TTI-C 1427 E. 60th Street)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20071004/e3208a02/attachment.html