A competitive analysis of the list update problem with lookahead

被引:28
作者
Albers, S [1 ]
机构
[1] Max Planck Inst Informat, D-66123 Saarbrucken, Germany
关键词
linear lists; on-line algorithms; competitive analysis; lookahead;
D O I
10.1016/S0304-3975(97)00026-1
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We consider the question of lookahead in the list update problem: What improvement can be achieved in terms of competitiveness if an on-line algorithm sees not only the present request to be served but also some future requests? We introduce two different models of lookahead and study the list update problem using these models. We develop lower bounds on the competitiveness that can be achieved by deterministic on-line algorithms with lookahead. Furthermore, we present on-line algorithms with lookahead that are competitive against static off-line algorithms. (C) 1998-Elsevier Science B.V. All rights reserved.
引用
收藏
页码:95 / 109
页数:15
相关论文
共 30 条
[1]   A COMBINED BIT AND TIMESTAMP ALGORITHM FOR THE LIST UPDATE PROBLEM [J].
ALBERS, S ;
VONSTENGEL, B ;
WERCHNER, R .
INFORMATION PROCESSING LETTERS, 1995, 56 (03) :135-139
[2]  
ALBERS S, 1995, PROCEEDINGS OF THE SIXTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P412
[3]  
ALBERS S, 1993, LECT NOTES COMPUTER, V726, P1
[4]   A NEW MEASURE FOR THE STUDY OF ONLINE ALGORITHMS [J].
BENDAVID, S ;
BORODIN, A .
ALGORITHMICA, 1994, 11 (01) :73-91
[5]   ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS [J].
BENDAVID, S ;
BORODIN, A ;
KARP, R ;
TARDOS, G ;
WIGDERSON, A .
ALGORITHMICA, 1994, 11 (01) :2-14
[6]   AMORTIZED ANALYSES OF SELF-ORGANIZING SEQUENTIAL SEARCH HEURISTICS [J].
BENTLEY, JL ;
MCGEOCH, CC .
COMMUNICATIONS OF THE ACM, 1985, 28 (04) :404-411
[7]   A LOCALLY ADAPTIVE DATA-COMPRESSION SCHEME [J].
BENTLEY, JL ;
SLEATOR, DD ;
TARJAN, RE ;
WEI, VK .
COMMUNICATIONS OF THE ACM, 1986, 29 (04) :320-330
[8]  
BENTLEY JL, 1990, PROCEEDINGS OF THE FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P179
[9]   HEURISTICS THAT DYNAMICALLY ORGANIZE DATA-STRUCTURES [J].
BITNER, JR .
SIAM JOURNAL ON COMPUTING, 1979, 8 (01) :82-110
[10]  
BRESLAUER D, 1996, LNCS, V1046, P593