Approximating disjoint-path problems using packing integer programs

• 成果类型: Article
• 署名作者: Kolliopoulos, SG; Stein, C
• 署名单位: McMaster University; Columbia University; Dartmouth College
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-002-0370-6
• 发表日期: 2004
• 页码: 63-87
• 关键词: algorithms; graphs; square; FLOW

摘要

In a packing integer program, we are given a matrix A and column vectors b,c with nonnegative entries. We seek a vector x of nonnegative integers, which maximizes c(T)x, subject to Axless than or equal tob. The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connection has largely been ignored in terms of approximation algorithms. We explore the topic of approximating disjoint-path problems using polynomial-size packing integer programs. Motivated by the disjoint paths applications, we introduce the study of a class of packing integer programs, called column-restricted. We develop improved approximation algorithms for column-restricted programs, a result that we believe is of independent interest. Additional approximation algorithms for disjoint-paths are presented that are simple to implement and achieve good performance when the input has a special structure.