MAXIMUM PRIORITY FLOW

• INSTANCE: Directed graph $G=\left(V,E\right)$, sources $s_1, \ldots, s_k \in V$, sinks $t_1, \ldots, t_k \in V$, a capacity function $c:E \rightarrow R$, a bound function $b: V \rightarrow R$, and, for any vertex v, a partial order on the set of edges leaving v.

• SOLUTION: A priority flow f, i.e., a function $f:E \rightarrow R$ such that (a) for any edge e, $f(e) \leq c(e)$, (b) for any vertex $v \in V-\{s_1, \ldots, s_k, t_1, \ldots, t_k\}$, 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 $e_1, e_2$ leaving v, if $f(e_1) < c(e_1)$ and $e_1$ is less than $e_2$, then $f(e_2)=0$.

• MEASURE: The amount of flow entering sink $t_1$, i.e., $\sum_{(x,t_1) \in E}f(x,t_1)$.

  
  

• Bad News: Not approximable within $2^{\theta(\log^p n)}$ for some p>0 unless NP $\subseteq \mbox{\sc Dtime}(n^{d\log^{1/\varepsilon }n})$ [67].

• Comment: Does not admit a PTAS.