Interleaved Prefetching

We consider the problem of interleaving sequences of positive and
negative numbers in order to maximize the minimum, over all prefixes
p of the interleaved sequence, of the sum of the numbers in p. A
simple and efficient offline solution is given. We also consider an
online version of the problem. Under a cost model suitable for the
prefetching application that motivates the problem, a strongly
competitive online algorithm is given. These problems abstract two
practical problems of scheduling data prefetches in a multiprogrammed
or multithreaded computing environment.

Also appeared in Algorithmica, vol. 32, no. 1, p. 107-22, January 2002