Approximating disjoint-path problems using packing integer programs

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 $Ax \leq b.$ 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.Work partially supported by NSERC OG 227809-00 and a CFI New Opportunities Award. Part of this work was done while at the Department of Computer Science, Dartmouth College and partially by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.This work was done while at the Department of Computer Science, Dartmouth College and partially supported by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.