Next: Miscellaneous
Up: Flow Problems
Previous: MINIMUM SINGLE-SINK EDGE INSTALLATION
  Index
- INSTANCE:
Graph
,
with edge capacities
,
source vertex s, collection of
sinks
with associated non-negative
integer demands
such that,
for all
and
.
- SOLUTION:
A single s-ti flow path for each commodity i so that the
demands are satisfied and the total flow routed across any edge
e is bounded by c(e).
- MEASURE:
,
where f(e) is the total flow
routed across e.
- Good News:
Approximable within 3.23 [314].
- Bad News:
Not approximable within 3/2
for any
[308].
- Comment:
Approximable within 3.23 also on directed graphs.
Variation in which the objective is to maximize the routable demand
is approximable within 14.
If the objective is to minimize the number of rounds in
which all demands are routed, is approximable within 13.
The generalized problem in which there are two source vertices
is not approximable within 2
[314].
Viggo Kann
1999-04-22