Approximation algorithms for disjoint paths and related routing and packing problems

• 成果类型: Article
• 署名作者: Baveja, A; Srinivasan, A
• 署名单位: Rutgers University System; Rutgers University Camden; Rutgers University New Brunswick; Alcatel-Lucent; Lucent Technologies; AT&T
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.25.2.255.12228
• 发表日期: 2000
• 页码: 255-280
• 关键词: expander graphs; selection; networks

摘要

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.