- 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 leaving*v*, if and is less than , then . - MEASURE:
The amount of flow entering sink ,
i.e.,
.

*Bad News:*Not approximable within for some*p>0*unless NP [67].*Comment:*Does not admit a PTAS.