Approximation algorithms for disjoint paths and related routing and packing problems
A Baveja, A Srinivasan - Mathematics of Operations …, 2000 - pubsonline.informs.org
Mathematics of Operations Research, 2000•pubsonline.informs.org
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.
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.
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.