Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems
01 November 2003
We study the approximability of two classes of network routing problems. The first class of problems in our study correspond to classical multicommodity flow problems of the following form: We are given a network G with integer capacities on its edges, together with source-sink pairs (s sub i, t sub i), 1