𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the competitiveness of the move-to-front rule

✍ Scribed by Conrado Martı́nez; Salvador Roura

Publisher
Elsevier Science
Year
2000
Tongue
English
Weight
183 KB
Volume
242
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the list access problem and show that one questionable assumption in the original cost model presented by Sleator and Tarjan (1985) and subsequent literature allowed for several competitiveness results of the move-to-front rule (MTF). We present an o -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.

📜 SIMILAR VOLUMES

On the distribution of search cost for t
On the distribution of search cost for the move-to-front rule
✍ James Allen Fill; Lars Holst 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB 👁 1 views

A file of records, each with an associated request probability, is dynamically maintained as a serial list. Successive requests are mutually independent. The list is reordered according to the move-to-front (MTF) rule: The requested record is moved to the front of the list. We derive the stationary

Limiting search cost distribution for th
Limiting search cost distribution for the move-to-front rule with random request probabilities
✍ Javiera Barrera; Thierry Huillet; Christian Paroissin 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 181 KB

Consider a list of n files whose popularities are random. The list is updated according to the move-to-front rule. When the induced Markov chain is at equilibrium, we explicitly compute the limiting distribution of the search-cost per item as n tends to infinity. The uniform distribution results in

Application of the EC competition rules
Application of the EC competition rules to access agreements in the telecommunications sector
✍ Susan Bright 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 357 KB

The European Commission finally published its Notice on the application of the competition rules to access agreements in the telecommunications sector in August 1998.1 A draft of the Notice was originally published in October 1996 and was followed by a period of public consultation.The purpose of th