Next:
MAXIMUM DISJOINT CONNECTING PATHS
Up:
Flow Problems
Previous:
MAXIMUM PRIORITY FLOW
 
Index
M
AXIMUM
I
NTEGRAL
K
-M
ULTICOMMODITY
F
LOW ON
T
REES
I
NSTANCE:
A tree
, a capacity function
and
k
pairs of vertices
.
S
OLUTION:
A flow
for each pair
with
such that, for each
,
where
if
e
belongs to the unique path from
and
, 0 otherwise.
M
EASURE:
The sum of the flows, i.e.,
.
Good News:
Approximable within 2 [
190
].
Bad News:
A
PX
-complete [
190
].
Comment:
Transformation from M
AXIMUM 3-
D
IMENSIONAL
M
ATCHING
. It remains A
PX
-complete even if the edge capacities are 1 and 2.
Viggo Kann
2000-03-20