Next: MAXIMUM DISJOINT CONNECTING PATHS
Up: Flow Problems
Previous: MAXIMUM PRIORITY FLOW
  Index
- INSTANCE:
A tree
,
a capacity function
and k pairs
of vertices (si,ti).
- SOLUTION:
A flow fi for each pair (si,ti) with
such that, for each
,
where qi(e)=1 if e
belongs to the unique path from si and ti, 0 otherwise.
- MEASURE:
The sum of the flows, i.e.,
.
- Good News:
Approximable within 2 [178].
- Bad News:
APX-complete [178].
- Comment:
Transformation from MAXIMUM 3-DIMENSIONAL
MATCHING.
It remains APX-complete even if the edge capacities are 1 and 2.
Viggo Kann
1999-04-22