Next: MINIMUM VEHICLE SCHEDULING ON Up: Miscellaneous Previous: MINIMUM FILE TRANSFER SCHEDULING Index

### MINIMUM SCHEDULE LENGTH

- 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 , f0(t)=u and fl(t)=v,

  2.
    for any and for any token t, if fi(t)=v and fi+1(t)=w then (a) , (b) , (c) , and (d) .

- MEASURE: The length of the schedule, i.e., l.

- Bad News: Not in APX [109].

- 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 [126].

Next: MINIMUM VEHICLE SCHEDULING ON Up: Miscellaneous Previous: MINIMUM FILE TRANSFER SCHEDULING Index