MINIMUM SCHEDULE LENGTH

• INSTANCE: A network $N=\left(V,E,b,c\right)$ where $G=\left(V,E\right)$ is a graph, $b:V \rightarrow N$ is the vertex-capacity function, and $c : E \rightarrow N$ is the edge-capacity function, and a set T of tokens $t=\left(u,v,p\right)$ where $u,v \in V$ and p is either a path from u to v or the empty set.

• SOLUTION: A schedule S, i.e., a sequence $f_0, \ldots, f_l$ of configuration functions $f_i:T \rightarrow V$ such that

  1.

  for any token $t=\left(u,v,p\right)$, $f_0(t)=u$ and $f_l(t)=v$,

  2.

  for any $0 \leq i \leq l-1$ and for any token t, if $f_i(t)=v$ and $f_{i+1}(t)=w$ then (a) $(u,v) \in E$, (b) $\vert\{t':f_i(t')=w\}\vert < b(w)$, (c) $\vert\{t':f_{i+1}(t')=w\}\vert \leq b(w)$, and (d) $\vert\{t':f_i(t')=v \wedge f_{i+1}(t')=w \}\vert \leq c(v,w)$.

• 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 $\vert T\vert^{1-\varepsilon }$ for any $\varepsilon$ [136].