Disjoint Paths in Networks
Department of Computer and Information Science,
University of Pennsylvania
Wednesday April 16th, 2008
Location: Sage 3510 - 4:00 p.m. to 5:00 p.m.
Refreshments at 3:30 p.m.
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.
Hosted by: Volkan Isler
Administrative support: Shannon Carrothers (x6354)
For more information:
Dr. Sanjeev Khanna's webpage
Last updated: March 11, 2008