Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/83338

On the competitiveness of the move-to-front rule
Roura Ferret, Salvador; Martínez Parra, Conrado
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
We consider the list access problem and show that one questionable assumption in the original cost model presented by Sleator and Tarjan (Amortized Efficiency of List Update and Paging Rules, CACM, 28(2):202-208, 1985) and subsequent literature allowed for several competitiveness results of the move-to-front rule (MTF). We present an off-line algorithm for the list access problem and prove that, under a more realistic cost model, no on-line algorithm can be c-competitive for any constant c, MTF included.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
MTF
Move-to -ront rule
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Kirschenhofer, P; Martínez Parra, Conrado; Prodinger, H
Duch Brown, Amalia; Lau Laynes-Lozada, Gustavo Salvador; Martínez Parra, Conrado
Mani, Anaga; Venkataramani, Divya; Petit Silvestre, Jordi; Roura Ferret, Salvador
Freixas Bosch, Josep; Molinero Albareda, Xavier; Roura Ferret, Salvador