Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
We consider the problem of interleaving sequences of positive and negative numbers in order to maximize the minimum, overall 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.
Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
Fausto Bernardini, Holly Rushmeier
Proceedings of SPIE - The International Society for Optical Engineering
Naga Ayachitula, Melissa Buco, et al.
SCC 2007
Nimrod Megiddo
Journal of Symbolic Computation