New Algorithms and Hardness Results for Disjoint Paths Problems

Sanjeev Khanna
Department of Computing and Information Science
University of Pennsylvania


Wednesday, August 3, 2005
4:30 - 5:45 PM
Terman Engineering Center, Room 217


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 route as many pairs as possible such that the paths assigned to the routed pairs do not share any network links. EDP and its variants have numerous applications including network routing, bandwidth allocation, and VLSI design. Not surprisingly, it is one of the most extensively studied optimization problems and is connected to major developments in algorithms and graph theory. In this talk, we will describe a new framework that gives substantially improved algorithms for EDP and related routing problems on undirected graphs. A central idea in the framework is that of decomposition of an arbitrary instance into "well-linked" instances. We will also describe some recent progress on hardness of EDP which gives polylogarithmic hardness results even when edge capacities are allowed to be violated. This is based on joint works with Chandra Chekuri, Julia Chuzhoy, and Bruce Shepherd.

---

Operations Research Colloquia: http://or.stanford.edu/oras_seminars.html