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_i,t_i), , such that a positive integer demand d_i and a positive ``profit'' r_i is associated with each pair. A feasible solution is a subset of the (s_i,t_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. In the special case when all demands, profits, and capacities equal one, both these variants reduce to the classical NP-hard edge-disjoint paths problem (referred to as EDP). An -approximation is known for USF under the assumption that , where m denotes the number of edges, denotes the maximum demand and denotes the minimum edge capacity (the approximation factor improves to for EDP. While it has been generally believed that these problems are very hard to approximate, only MAX SNP-hardness was known thus far. We prove here the tight result that in directed graphs, for any , EDP (and hence also USF), is NP-hard to approximate within . We also give a simple -approximation algorithm for USF under the assumption that , and an -approximation when the only assumption is that is polynomially bounded. Our algorithms also turn out to be much simpler than the existing ones. The hardness result for EDP trivially implies an identical result for approximating ISF on directed networks. On the algorithmic side, we give a simple greedy algorithm that gives a -approximation for ISF. for the special case of unit capacities, we are able to give a corresponding algorithm achieving a factor , but for the general case we only achieve a factor of where , and a factor of if .

The second class of routing problems in our study is another well known one: the goal here is to find a maximum number of length bounded edge-disjoint paths between given source-sink pairs in a graph G. We refer to this problem as the bounded length edge-disjoint paths (BLEDP) problem. We show that, for any ,BLEDP is hard to approximate within even on undirected graphs. On the algorithmic side, we give an -approximation algorithm for BLEDP. We also consider a special case of BLEDP, which we refer to as (s,t)-BLEDP, in which there is only one source-sink pair. Without the length restriction, this problem reduces to the polynomial-time solvable max-flow problem. However, with the length restriction, we show that this problem is hard to approximate within , for any , in directed graphs and MAX SNP-hard in undirected graphs even when the length bound is a (small) constant.

Postscript