** Next:** About this document ...

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

** Next:** About this document ...
*Rajmohan Rajaraman*

*4/12/1999*