A COMBINED BIT AND TIMESTAMP ALGORITHM FOR THE LIST UPDATE PROBLEM

被引：37

作者：

ALBERS, S ^{[1
]}

VONSTENGEL, B ^{[1
]}

WERCHNER, R ^{[1
]}

机构：

[1] INT COMP SCI INST,BERKELEY,CA 94704

来源：

INFORMATION PROCESSING LETTERS | 1995年 / 56卷 / 03期

关键词：

ONLINE ALGORITHMS; ANALYSIS OF ALGORITHMS; COMPETITIVE ANALYSIS; LIST-UPDATE;

D O I：

10.1016/0020-0190(95)00142-Y

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present a randomized on-line algorithm for the list update problem which achieves a competitive factor of 1.6, the best known so far. The algorithm makes an initial random choice between two known algorithms that have different worst-case request sequences. The first is the BIT algorithm that, for each item in the list, alternates between moving it to the front of the list and leaving it at its place after it has been requested. The second is a TIMESTAMP algorithm that moves an item in front of less often requested items within the list.

引用

页码：135 / 139

页数：5

共 8 条

[1]

ALBERS S, 1995, 6TH P ANN ACM SIAM S, P412

[2] ON THE POWER OF RANDOMIZATION IN ONLINE ALGORITHMS [J].