SS18 M INIMUM F ILE T RANSFER S CHEDULING

   
• I NSTANCE : A file transfer graph, i.e., a graph , a port constraint function and a file length function .
• S OLUTION : A file transfer schedule, i.e., a function such that, for each vertex v and for each ,

  
  
  

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

• Good News: Approximable within 2.5 [ 80 ].
• Comment: Several special cases with better guarantees are also obtainable [ 80 ].