MINIMUM FILE TRANSFER SCHEDULING

• INSTANCE: A file transfer graph, i.e., a graph $G=\left(V,E\right)$, a port constraint function $p: V \rightarrow N$ and a file length function $L: E \rightarrow N$.

• SOLUTION: A file transfer schedule, i.e., a function $s: E\rightarrow N$ such that, for each vertex v and for each $t \in N$,

  
  

  $$\vert\{u : (u,v) \in E \wedge s(e) \leq t \leq s(e)+L(e)\}\vert \leq p(v).$$
  
  

• MEASURE: The makespan of the schedule, i.e., $\max_{e \in E}(s(e)+L(e))$.

  
  

• Good News: Approximable within 2.5 [121].

• Comment: Several special cases with better guarantees are also obtainable [121].