Next: MINIMUM VEHICLE SCHEDULING ON
Up: Miscellaneous
Previous: MINIMUM FILE TRANSFER SCHEDULING
  Index
- INSTANCE:
A network
where
is a graph,
is the vertex-capacity function, and
is the
edge-capacity function, and a set T of tokens
where
and p is either a path from u to v or the empty set.
- SOLUTION:
A schedule S, i.e., a sequence
of configuration functions
such that
- 1.
- for any token
,
and
,
- 2.
- for any
and for any token t, if
and
then (a)
,
(b)
,
(c)
,
and (d)
.
- MEASURE:
The length of the schedule, i.e., l.
- Bad News:
Not in APX [117].
- Comment:
Reduction from MINIMUM GRAPH COLORING.
It remains non-approximable even for layered graphs.
The variation in which the vertex-capacity is unbounded and the delay,
i.e., the maximum number of times a token is neither in the final
destination nor moved, must be minimized is also non-approximable
within
for any
[136].
Next: MINIMUM VEHICLE SCHEDULING ON
Up: Miscellaneous
Previous: MINIMUM FILE TRANSFER SCHEDULING
  Index
Viggo Kann
2000-03-20