On Multi-threaded Metrical Task Systems

Alborzi, 2001, The k-client problem, J. Algorithms, 41, 115, 10.1006/jagm.2001.1182 Ausiello, 2001, Algorithms for the on-line travelling salesman, Algorithmica, 29, 560, 10.1007/s004530010071 Y. Bartal, A. Blum, C. Burch, A. Tomkins, A polylog(n)-competitive algorithm for metrical task systems, in: Proc. 29th ACM Symposium on Theory of Computing, 1997, pp. 711–719 Barve, 2000, Application-controlled paging for a shared cache, SIAM J. Comput., 29, 1290, 10.1137/S0097539797324278 Ben-David, 1994, On the power of randomization in on-line algorithms, Algorithmica, 11, 2, 10.1007/BF01294260 Blum, 2001, A decomposition theorem for task systems and bounds for randomized server problems, SIAM J. Comput., 30, 1624, 10.1137/S0097539799351882 Borodin, 1995, Competitive paging with locality of reference, J. Comput. System Sci., 50, 244, 10.1006/jcss.1995.1021 Borodin, 1992, An optimal on-line algorithm for metrical task system, J. ACM, 39, 745, 10.1145/146585.146588 Burley, 1997, On algorithm design for metrical task systems, Algorithmica, 18, 461, 10.1007/PL00009166 P. Cao, E.W. Felten, K. Li, Application-controlled file caching policies, in: Proc. Summer USENIX Conference, 1994 E. Feuerstein, On-line paging of structured data and multi-threaded paging, PhD thesis, Università degli Studi di Roma “La Sapienza”, 1995 Feuerstein, 2003, On-line multi-threaded scheduling, J. Scheduling, 6, 167, 10.1023/A:1022987804726 E. Feuerstein, D.G. Robak, A. Strejilevich de Loma, Manuscript, 2000 E. Feuerstein, M. Seleson, A. Strejilevich de Loma, Manuscript, 2000 Feuerstein, 2001, On-line single-server dial-a-ride problems, Theoret. Comput. Sci., 268, 91, 10.1016/S0304-3975(00)00261-9 Feuerstein, 2002, On-line multi-threaded paging, Algorithmica, 32, 36, 10.1007/s00453-001-0073-z A. Fiat, A.R. Karlin, Randomized and multipointer paging with locality of reference, in: Proc. Twenty-Seventh Annual ACM Symposium on the Theory of Computing, Las Vegas, 29 May–1 June 1995, pp. 626–634 Karlin, 1988, Competitive snoopy caching, Algorithmica, 3, 79, 10.1007/BF01762111 Kimbrel, 2002, Interleaved prefetching, Algorithmica, 32, 107, 10.1007/s00453-001-0066-y Manasse, 1990, Competitive algorithms for server problems, J. Algorithms, 11, 208, 10.1016/0196-6774(90)90003-W McGeoch, 1991, A strongly competitive randomized paging algorithm, Algorithmica, 6, 816, 10.1007/BF01759073 Seiden, 1999, Randomized online multi-threaded paging, Nordic J. Comput., 6, 148 M. Seleson, On-line multi-threaded dial-a-ride, Master's thesis, Universidad de Buenos Aires, Departamento de Computación, July 1999 Sleator, 1985, Amortized efficiency of list update and paging rules, Comm. ACM, 28, 202, 10.1145/2786.2793 Strejilevich de Loma, 1998, New results on fair multi-threaded paging, Electronic J. SADIO, 1, 21