Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems

Abstract

We study the approximability of two classes of network routing problems. The first class of problems in our study corre spend 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 (a, ti), 1 5 i 2 k, such that a positive integer demand di and a positive "profit" t'i is associated with eah pair. A feasible solution is a subset S of the (sir ti) 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