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 条

[21] LIST ORGANIZING STRATEGIES USING STOCHASTIC MOVE-TO-FRONT AND STOCHASTIC MOVE-TO-REAR OPERATIONS
OOMMEN, BJ
HANSEN, ER
SIAM JOURNAL ON COMPUTING, 1987, 16 (04) : 705 - 716
[22] The performance of the move-to-front scheme under some particular forms of Markov requests
Rodrigues, ER
JOURNAL OF APPLIED PROBABILITY, 1995, 32 (04) : 1089 - 1102
[23] Lossless audio coding using Burrows-Wheeler transform and move-to-front coding
Elsayed, Hend Ali
Alghoniemy, Masoud
2007 INTERNATIONAL CONFERENCE ON COMPUTER ENGINEERING & SYSTEMS: ICCES '07, 2007, : 209 - 212
[24] THE LIMITING MOVE-TO-FRONT SEARCH-COST IN LAW OF LARGE NUMBERS ASYMPTOTIC REGIMES
Barrera, Javiera
Fontbona, Joaquin
ANNALS OF APPLIED PROBABILITY, 2010, 20 (02): : 722 - 752
[25] A Real-Time Program Trace Compressor Utilizing Double Move-to-Front Method
Uzelac, Vladimir
Milenkovic, Aleksandar
DAC: 2009 46TH ACM/IEEE DESIGN AUTOMATION CONFERENCE, VOLS 1 AND 2, 2009, : 738 - 743
[26] Lossless compression of binary image using move-to-front transform and two-role encoder
Benzid, R.
ELECTRONICS LETTERS, 2011, 47 (02) : 104 - +
[27] Chain code lossless compression using move-to-front transform and adaptive run-length encoding
Zalik, Borut
Lukac, Niko
SIGNAL PROCESSING-IMAGE COMMUNICATION, 2014, 29 (01) : 96 - 106
[28] Burrows-Wheeler Transform and Combination of Move-to-Front Coding and Run Length Encoding for Lossless Audio Coding
Elsayed, Hend. A.
2014 9TH INTERNATIONAL CONFERENCE ON COMPUTER ENGINEERING & SYSTEMS (ICCES), 2014, : 354 - 359
[29] Lossy and lossless spectral Image compression using Quaternion Fourier, Burrows-Wheeler and Move-to-Front Transforms
Liu, Yang
Goutte, Robert
PROCEEDINGS OF 2012 IEEE 11TH INTERNATIONAL CONFERENCE ON SIGNAL PROCESSING (ICSP) VOLS 1-3, 2012, : 619 - +
[30] Asymptotic approximation of the move-to-front search cost distribution and least-recently used caching fault probabilities
Jelenkovic, PR
ANNALS OF APPLIED PROBABILITY, 1999, 9 (02): : 430 - 464

← 1 2 3 4 5 →