Colloquia

Sanjeev Khanna

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.

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.

Hosted by: Volkan Isler
Administrative support: Shannon Carrothers (x6354)

For more information:

Dr. Sanjeev Khanna's webpage

Last updated: March 11, 2008