Peter Winkler

Dartmouth/MSRI

A "schedule" for two sequences a_{0},...,a_{m} and b_{0},...,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!