Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems

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 = i = k such that a positive integer demand d sub i and a positive "profit" r sub i is associated with each pair. A feasible solution is a subset S of the (s sub i, t sub i) pairs such that demands associated with pairs in S can be fully met through a routing which respects all capacity constraints, and the objective is to maximize the total profit associated with the satisfied pairs. We consider two natural variants: unsplittable flow (USF) where each pair must be satisfied by routing all its demand on a single path, and integral splittable flow (ISF) where the flow satisfying a demand can be split in several paths, each carrying an integral amount of flow.