Title: New Algorithms and Hardness Results for Disjoint Paths Problem
Speaker: Sanjeev Khanna , University of Pennsylvania
Date: April 26, 2005 2:00-3:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
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. We will describe a new framework for undirected graphs that provides substantially improved algorithms for several routing problems. The key notion of the framework is that of a "well-linked" set of terminals. The talk will highlight the framework, its applications to EDP and other routing problems, and connections to treewidth and multicommodity maxflow-mincut theorems. We will also briefly describe some recent progress on hardness of EDP which gives polylogarithmic hardness results even when congestion is allowed.
This is based on joint works with Chandra Chekuri, Julia Chuzhoy, and Bruce Shepherd.