Scheduling Sequences of Reals

Peter Winkler 
Dartmouth/MSRI

A "schedule" for two sequences a₀,...,a_m and b₀,...,b_n is a lattice path {(x_i,y_i)}_{{i=0,...,m+n}} from (0,0) to (m,n). With dynamic programming one can  find a schedule which minimizes max_i(a_{x_i} + b_{y_i}), but, even better, one can find a schedule which is optimal in  the sense that it needn't change when more sequences have  to be added. One consequence is that a variable number of  such sequences can be optimally scheduled in polynomial  time.

WARNING: this is ongoing work some or all of which may  already be known!