SS2 M INIMUM S TORAGE -T IME S EQUENCING

   
• I NSTANCE : Set T of tasks, a directed acyclic graph defining precedence constraints for the tasks, for each task a length , and for each edge in the graph a weight measuring the storage required to save the intermediate results generated by task until it is consumed by task .
• S OLUTION : A one-processor schedule for T that obeys the precedence constraints, i.e., a permutation such that, for each edge , .
• M EASURE : The total storage-time product, i.e.,
  
  

• Good News: Approximable within [ 308 ].