Next: MAXIMUM INTEGRAL K-MULTICOMMODITY FLOW
Up: Flow Problems
Previous: Flow Problems
  Index
- 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.
Viggo Kann
2000-03-20