SS19 M INIMUM S CHEDULE L ENGTH

   
• I NSTANCE : 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.
• S OLUTION : 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) .

• M EASURE : The length of the schedule, i.e., l .

• Bad News: Not in A PX [ 78 ].
• Comment: Reduction from M INIMUM G RAPH C OLORING . 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 [ 183 ].