New Algorithms and Insights for Routing Problems

Prof. Chekuri is from Lucent Technologies Laboratory
A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a network (graph) and a collection of source-destination pairs in the network. The objective is to decide if all the pairs can be connected by edge-disjoint paths. This problem is NP-Complete and we study approximation algorithms for the optimization problem where the goal is to maximize the number of pairs that can be connected (routed). EDP and its variants have numerous applications including routing and bandwidth allocation in networks and VLSI design. In addition, these routing problems have inspired a number of major developments in algorithms and graph theory.

We will describe a new framework that provides substantially improved algorithms and new insights for several routing problems including EDP. The talk will highlight the framework, its algorithmic applications, and connections to treewidth and multicommodity maxflow-mincut theorems.

Joint work with Sanjeev Khanna (U. Penn) and Bruce Shepherd (Bell Labs).