New Algorithms for Disjoint Paths Problems
Speaker: Sanjeev Khanna , University of Pennsylvania
Date: December 13 2005
Time: 4:15PM to 5:15PM
Location: 32-G449 (Kiva)
Host: Piotr Indyk, MIT/CSAIL
Contact: Piotr Indyk, indyk@mit.edu
Relevant URL: 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 maximize the number of pairs that can be connected by edge-disjoint paths. In this talk, we describe some new approximation algorithms for EDP and related routing problems obtained via the multicommodity flow relaxation. It is known that the integrality gap of this relaxation is polynomially large even on grid graphs. To overcome this inherent barrier, we consider algorithms that can use constant congestion.
We show that the flow relaxation can be used to reduce an instance of the routing problem to a collection of instances with special structure, called well-linked instances. Consequently, it is sufficient to design a good rounding algorithm for a well-linked instance. We illustrate the strength of this approach by obtaining an approximation algorithm for EDP in undirected planar graphs with a logarithmic ratio (using congestion 2). This improves upon earlier polynomial ratio algorithms (for any constant congestion).
Extending our approach to general graphs hinges on resolving an interesting graph-theoretic question. A resolution of this question would also settle the integrality gap of the flow relaxation (up to poly-logarithmic factors).
Joint work with Chandra Chekuri and Bruce Shepherd.
See other events that are part of Theory Colloquium Fall 2005
See other events happening in December 2005
