The All-or-Nothing Multicommodity Flow Problem
Authors:
- Chandra ChekuriCCChandra Chekuri
- Sanjeev KhannaSKSanjeev Khanna
- F. Bruce ShepherdFSF. Bruce Shepherd
- 1 January 2013
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 42 (4) , 1467-1493
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 a set of $k$ node pairs $s_1 t_1, s_2t_2, \ldots ,s_kt_k$. Each pair has a unit demand. A subset $S$ of $\{1,2,\ldots,k\}$ is routable if there is a multicommodity flow in $G$ that simultaneously sends one unit of flow between $s_i$ and $t_i$ for each $i$ in $S$. Note that this differs from the edge-disjoint path problem (edp) in that we do not insist on integral flows for the pairs. The objective is to find a maximum routable subset $S$. When $G$ is a capacitated tree, the problem already generalizes $b$-matchings, and even in this case it is NP-hard and APX-hard to approximate. For trees, a $2$-approximation is known for the cardinality case and a $4$-approximation for the weighted case. In this paper we show that the natural linear programming relaxation for the all-or-nothing flow problem has a polylogarithmic integrality gap in general undirected graphs. This is in sharp contrast to edp, where the gap is known to be $\Theta(\sqrt{n})$; this ratio is also the best approximation ratio currently known for edp. Our algorithm extends to the case where each pair $s_it_i$ has a demand $d_i$ associated with it and we need to completely route $d_i$ to get credit for pair $i$; we assume that the maximum demand of the pairs is at most the minimum capacity of the edges. 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 and the accepted pairs have to be routed. We obtain a randomized algorithm which has a polylogarithmic competitive ratio for maximizing throughput of the accepted requests if it is allowed to violate edge capacities by a $(2+\epsilon)$ factor.
Keywords
This publication has 23 references indexed in Scilit:
- Inapproximability of Edge-Disjoint Paths and low congestion routing on undirected graphsCombinatorica, 2010
- A Note on Multiflows and TreewidthAlgorithmica, 2007
- Improved bounds for the unsplittable flow problemJournal of Algorithms, 2006
- Approximation Algorithms for the Unsplittable Flow ProblemAlgorithmica, 2006
- Optimal oblivious routing in polynomial timeJournal of Computer and System Sciences, 2004
- Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problemsJournal of Computer and System Sciences, 2003
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- A Pushing-Pulling Method: New Proofs of Intersection TheoremsCombinatorica, 1999
- On-line routing of virtual circuits with applications to load balancing and machine schedulingJournal of the ACM, 1997
- Competitive routing of virtual circuits in ATM networksIEEE Journal on Selected Areas in Communications, 1995