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. 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, based on the flow relaxation of EDP, for getting much improved algorithms for undirected EDP. 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.

Biography

Sanjeev Khanna is a Rosenbluth Faculty Fellow and Professor in the Computer and Information Science Department at the University of Pennsylvania. He received a PhD in Computer Science from Stanford University (1996), a Master's degree in Computer Science from University of Illinois at Urbana-Champaign (1992), and a Bachelor's degree in Computer Science from Birla Institute of Technology, India (1990). His research interests are in approximation algorithms and hardness of approximation.

In recognition of his work, Sanjeev Khanna was awarded a Guggenheim Fellowship in 2007. His other awards include an IBM Faculty Fellowship(2007), an NSF Career award (2001), an Alfred P. Sloan Foundation Fellowship (2000), and an Arthur Samuel Dissertation Award from Stanford University (1996).

Back