Scheduling Sequences of Reals

Peter Winkler 

A "schedule" for two sequences a0,...,am and b0,...,bn is a lattice path {(xi,yi)}{i=0,...,m+n} from (0,0) to (m,n). With dynamic programming one can  find a schedule which minimizes maxi(ax_i + by_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!