The all-or-nothing multicommodity flow problem

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd

Research output: Contribution to journalConference articlepeer-review

Abstract

We consider the all-or-nothing multicommodity flow problem in general graphs. We are given a capacitated undirected graph G = (V, E, u) and set of k pairs s1t1, s2t2..., s ktk. Each pair has a unit demand. The objective is to find a largest subset S of {1, 2,...,k} such that for every i in S we can send a flow of one unit between si and ti. Note that this differs from the edge-disjoint path problem (EDP) in that we do not insist on integral flows for the pairs. This problem is NP-hard, and APX-hard, even on trees. For trees, a 2-approximation is known for the cardinality case and a 4-approximation for the weighted case. In this paper we build on a recent result of Räcke on low congestion oblivious routing in undirected graphs to obtain a poly-logarithmic approximation for the all-or-nothing problem in general undirected graphs. The best previous known approximation for all-or-nothing flow problem was O(min(n2/3, √m)), the same as that for EDP. Our algorithm extends to the case where each pair siti has a demand di associated with it and we need to completely route d i to get credit for pair i. We also consider the online admission control version where pairs arrive online and the algorithm has to decide immediately on its arrival whether to accept it or not. We obtain a randomized algorithm with a competitive ratio that is similar to the approximation ratio for the offline algorithm.

Original languageEnglish (US)
Pages (from-to)156-165
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 2004
Externally publishedYes
EventProceedings of the 36th Annual ACM Symposium on Theory of Computing - Chicago, IL, United States
Duration: Jun 13 2004Jun 15 2004

Keywords

  • All-or-Nothing Multicommodity flow
  • Approximation Algorithms
  • Edge Disjoint Paths
  • Multicommodity Flow
  • Oblivious Routing
  • Online Algorithms

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'The all-or-nothing multicommodity flow problem'. Together they form a unique fingerprint.

Cite this