Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
- 1 May 2000
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 25 (2) , 255-280
- https://doi.org/10.1287/moor.25.2.255.12228
Abstract
Given a network and a set of connection requests on it, we consider the maximum edge-disjoint paths and related generalizations and routing problems that arise in assigning paths for these requests. We present improved approximation algorithms and/or integrality gaps for all problems considered; the central theme of this work is the underlying multicommodity flow relaxation. Applications of these techniques to approximating families of packing integer programs are also presented.Keywords
This publication has 26 references indexed in Scilit:
- Approximations for the Disjoint Paths Problem in High-Diameter Planar NetworksJournal of Computer and System Sciences, 1998
- Efficient routing in optical networksJournal of the ACM, 1996
- On-Line Algorithms for Path Selection in a Nonblocking NetworkSIAM Journal on Computing, 1996
- Existence and Construction of Edge-Disjoint Paths on Expander GraphsSIAM Journal on Computing, 1994
- Packet routing and job-shop scheduling inO(congestion+dilation) stepsCombinatorica, 1994
- An O (log N ) deterministic packet-routing schemeJournal of the ACM, 1992
- A useful elementary correlation inequalityJournal of Combinatorial Theory, Series A, 1989
- Probabilistic construction of deterministic algorithms: Approximating packing integer programsJournal of Computer and System Sciences, 1988
- On a combinatorial gameJournal of Combinatorial Theory, Series A, 1973
- Correlation inequalities on some partially ordered setsCommunications in Mathematical Physics, 1971