Volume 2 (2006)
Article 7 pp. 137-146
An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow
Received: December 8, 2005
Published: May 4, 2006
Published: May 4, 2006
Keywords: edge disjoint paths, unsplittable flow, routing, approximation algorithm, integrality gap, undirected graphs, directed acyclic graphs
Categories: short, combinatorial optimization, algorithms, approximation algorithms, graphs, integrality gap, networks, routing
ACM Classification: C.2.0, F.2.2, G.1.6, G.3
AMS Classification: 68W20, 68W25, 90C59
Abstract: [Plain Text Version]
We consider the maximization version of the edge-disjoint path
problem (EDP). In undirected graphs and directed acyclic graphs, we
obtain an O(√n) upper bound on the
approximation ratio where
n is the number of nodes in the graph. We show this by
establishing the upper bound on the integrality gap of the natural
relaxation based on multicommodity flows. Our upper bound matches
within a constant factor a lower bound of Ω(√n) that
is known for both undirected and directed acyclic graphs.
The best previous upper bounds on the integrality gaps were
O(min{n2/3, √m}) for undirected graphs and
O(min{√(n log n), √m})
for directed acyclic graphs;
here m is the number of edges in the graph. These bounds are also
the best known approximation ratios for these problems.
Our bound also extends to
the unsplittable flow problem (UFP) when the maximum demand is at
most the minimum capacity.

Licensed under a Creative Commons License