Multicommodity flow, well-linked terminals, and routing problems

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd

Research output: Contribution to journalConference article

Abstract

We study multicommodity routing problems in both edge and node capacitated undirected graphs. The input to each problem is a capacitated graph G = (V, E) and a set Τ of node pairs. In the simplest setting, the goal is to route a unit of flow for as many pairs as possible subject to the edge (node) capacity constraints. If the flow for a routed pair is required to be along a single path, it is the well-studied disjoint paths problem. If we allow fractional routings of the flow, it is known as the all-or-nothing flow problem, The nodes in Τ are referred to as terminals. In recent work [8, 9], the authors obtained the first polylogarithmic approximation algorithms for some edge routing problems. A key idea in these algorithms is to decompose an instance into a collection of instances in which the terminals are well-linked. Informally speaking, a set of nodes is well-linked in a graph if it does not have small separators. A decomposition into well-linked instances was previously achieved in [8] via Räcke's hierarchical graph decomposition for oblivious routing [32]. In this paper, we design a simple new decomposition algorithm that is based on computing sparse cuts in a graph. Our new algorithm improves the earlier results for edge routing problems. Another important advantage of the algorithm is that it also applies to node-capacitated problems. We note that for oblivious routing with node capacities, an Ω(√n) lower bound is known on the congestion [18], and hence the oblivious routing approach cannot yield poly-logarithmic bounds for well-linked decompositions. Using the new decomposition, we obtain a poly-logarithmic approximation for the node capacitated allor-nothing flow problem in general graphs and node-disjoint path problem in planar graphs with O(1) congestion. We also show that the flow-cut gap for product multicommodity flows in node capacitated planar graphs is O(1), improving upon the O(log n) bound from [28].

Original languageEnglish (US)
Pages (from-to)183-192
Number of pages10
JournalProceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - Dec 1 2005
Externally publishedYes
Event13th Color Imaging Conference: Color Science, Systems, Technologies, and Applications - Scottsdale, AZ, United States
Duration: Nov 7 2005Nov 11 2005

Keywords

  • All-or-Nothing Plow
  • Disjoint Paths
  • Flow-Cut Gaps
  • Multicommodity Flow
  • Network Routing

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Multicommodity flow, well-linked terminals, and routing problems'. Together they form a unique fingerprint.

  • Cite this