On the competitiveness of the move-to-front rule

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/83338

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Roura Ferret, Salvador
dc.contributor.author	Martínez Parra, Conrado
dc.date	1996-11
dc.identifier.citation	Roura, S., Martinez, C. "On the competitiveness of the move-to-front rule". 1996.
dc.identifier.uri	http://hdl.handle.net/2117/83338
dc.language.iso	eng
dc.relation	LSI-96-63-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	MTF
dc.subject	Move-to -ront rule
dc.title	On the competitiveness of the move-to-front rule
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	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.