Next: MAXIMUM DISJOINT CONNECTING PATHS Up: Flow Problems Previous: MAXIMUM PRIORITY FLOW Index

### MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW ON TREES

- 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.