RANDOMIZED COMPETITIVE ALGORITHMS FOR THE LIST UPDATE PROBLEM

被引:59
作者
REINGOLD, N
WESTBROOK, J
SLEATOR, DD
机构
[1] YALE UNIV,DEPT COMP SCI,NEW HAVEN,CT 06520
[2] CARNEGIE MELLON UNIV,PITTSBURGH,PA 15213
关键词
SEQUENTIAL SEARCH; LIST-UPDATE; ONLINE ALGORITHMS; COMPETITIVE ANALYSIS; RANDOMIZED ALGORITHMS;
D O I
10.1007/BF01294261
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more competitive than the best previous randomized algorithm due to Irani. Our algorithm uses randomness only during an initialization phase, and from then on runs completely deterministically. It is the first randomized competitive algorithm with this property to beat the deterministic lower bound. We generalize our approach to a model in which access costs are fixed but update costs are scaled by an arbitrary constant d. We prove lower bounds for deterministic list update algorithms and for randomized algorithms against oblivious and adaptive on-line adversaries. In particular, we show that for this problem adaptive on-line and adaptive off-line adversaries are equally powerful.
引用
收藏
页码:15 / 32
页数:18
相关论文
共 26 条
[21]  
RAGHAVAN P, 1990, RC15622 IBM TJ WATS
[22]  
REINGOLD N, 1990, YALEUDCSTR805 YAL U
[23]   SELF-ORGANIZING SEQUENTIAL SEARCH HEURISTICS [J].
RIVEST, R .
COMMUNICATIONS OF THE ACM, 1976, 19 (02) :63-67
[24]   AMORTIZED EFFICIENCY OF LIST UPDATE AND PAGING RULES [J].
SLEATOR, DD ;
TARJAN, RE .
COMMUNICATIONS OF THE ACM, 1985, 28 (02) :202-208
[25]  
Westland J. C., 1991, Proceedings of the Twenty-Fourth Annual Hawaii International Conference on System Sciences (Cat. No.91TH0350-9), P135, DOI 10.1109/HICSS.1991.184137
[26]  
[No title captured]