Next: MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW Up: Flow Problems Previous: Flow Problems Index

### MAXIMUM PRIORITY FLOW

- INSTANCE: Directed graph , sources , sinks , a capacity function , a bound function , and, for any vertex v, a partial order on the set of edges leaving v.

- SOLUTION: A priority flow f, i.e., a function such that (a) for any edge e, , (b) for any vertex , the flow is conserved at v, (c) for any vertex v, the flow leaving v is at most b(v), and (d) for any vertex v and for any pair of edges e1, e2 leaving v, if f(e1) < c(e1) and e1 is less than e2, then f(e2)=0.

- MEASURE: The amount of flow entering sink t1, i.e., .

- Bad News: Not approximable within for some p>0 unless NP [62].

- Comment: Does not admit a PTAS.