On the competitiveness of the move-to-front rule

被引：10

作者：

Martínez, C ^{[1
]}

Roura, S ^{[1
]}

机构：

[1] Univ Politecn Cataluna, Dept Llenguages & Sistemes Informat, E-08034 Barcelona, Spain

来源：

THEORETICAL COMPUTER SCIENCE | 2000年 / 242卷 / 1-2期

关键词：

competitive analysis; on-line algorithms; list update problem; move-to-front rule;

D O I：

10.1016/S0304-3975(98)00264-3

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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 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, MTT: included. (C) 2000 Elsevier Science B.V. All rights reserved.

引用

页码：313 / 325

页数：13

共 50 条

[1] On the distribution of search cost for the move-to-front rule
Fill, JA
Holst, L
RANDOM STRUCTURES & ALGORITHMS, 1996, 8 (03) : 179 - 186
[2] Move-to-front rule for accessing several records
Chong, KS
PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES, 1999, 13 (01) : 75 - 93
[3] On the distribution of the search cost for the move-to-front rule with random weights
Barrera, J
Paroissin, C
JOURNAL OF APPLIED PROBABILITY, 2004, 41 (01) : 250 - 262
[4] An exact formula for the move-to-front rule for self-organizing lists
Fill, JA
JOURNAL OF THEORETICAL PROBABILITY, 1996, 9 (01) : 113 - 160
[5] On a conjecture of Fill and Holst involving the move-to-front rule and cache faults
Hildebrand, M
PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES, 1999, 13 (03) : 377 - 385
[6] The move-to-front rule: A case study for two perfect sampling algorithms
Fill, JA
PROBABILITY IN THE ENGINEERING AND INFORMATIONAL SCIENCES, 1998, 12 (03) : 283 - 302
[7] Limiting search cost distribution for the move-to-front rule with random request probabilities
Barrera, Javiera
Huillet, Thierry
Paroissin, Christian
OPERATIONS RESEARCH LETTERS, 2006, 34 (05) : 557 - 563
[8] Limits and rates of convergence for the distribution of search cost under the move-to-front rule
Fill, JA
THEORETICAL COMPUTER SCIENCE, 1996, 164 (1-2) : 185 - 206
[9] Limiting behavior of the search cost distribution for the move-to-front rule in the stable case
Leisen, Fabrizio
Lijoi, Antonio
Paroissin, Christian
STATISTICS & PROBABILITY LETTERS, 2011, 81 (12) : 1827 - 1832
[10] On the move-to-front scheme with Markov dependent requests
Phatarfod, RM
Pryde, AJ
Dyte, D
JOURNAL OF APPLIED PROBABILITY, 1997, 34 (03) : 790 - 794

← 1 2 3 4 5 →