Paper Info
Title
Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems
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.
Year
DOI
Venue
2000
10.1287/moor.25.2.255.12228
Math. Oper. Res.
Keywords
DocType
Volume
Disjoint Paths,Related Routing,maximum edge-disjoint path,related generalization,Approximation Algorithms,approximation algorithm,assigning path,central theme,integrality gap,underlying multicommodity flow relaxation,connection request,integer program,Packing Problems,approximating family
Journal
25
Issue
ISSN
Citations 
2
0364-765X
46
PageRank 
References 
Authors
3.64
28
2
Name
Order
Citations
PageRank
Alok Baveja112011.99
Aravind Srinivasan23531291.42