ND42 M AXIMUM P RIORITY F LOW

   
• I NSTANCE : 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 .
• S OLUTION : 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 .
• M EASURE : The amount of flow entering sink , i.e., .

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