Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, (1428) Capital Federal, Argentina; e-mail: asdel@dc.uba.ar |
In this paper we reduce the existing gaps between the known lower and upper bounds for the competitiveness of on-line algorithms for the fair version of MTP. We treat some particular situations, with finite and infinite input sequences. We prove higher lower bounds and present a new on-line algorithm. We close the gap for the case in which the cache can hold only one page; surprisingly, we obtain different bounds for even and odd number of sequences; we prove that any lazy algorithm achieves the on-line lower bound when the number of sequences is odd.
Research supported in part by EC project DYNDATA under program KIT, and by UBACyT projects ``Algoritmos Eficientes para Problemas On-line con Aplicaciones'' and ``Modelos y Técnicas de Optimización Combinatoria".