%0 Journal Article
%J Mathematics of Operations ResearchMathematics of Operations Research
%D 2000
%T Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
%A Baveja,Alok
%A Srinivasan, Aravind
%K Approximation algorithms
%K Disjoint paths
%K integer programming
%K Linear programming
%K multicommodity flow
%K Packing
%K randomized algorithms
%K rounding
%K Routing
%K unsplittable flow
%X 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.
%B Mathematics of Operations ResearchMathematics of Operations Research
%V 25
%P 255 - 280
%8 2000/05/01/
%@ 0364-765X, 1526-5471
%G eng
%U http://mor.journal.informs.org/content/25/2/255
%N 2
%R 10.1287/moor.25.2.255.12228