A new lower bound for the list update problem in the partial cost model

被引：5

作者：

Ambühl, C

Gärtner, B

von Stengel, B

机构：

[1] Univ London London Sch Econ & Polit Sci, Dept Math, London WC2A 2AE, England

[2] Swiss Fed Inst Technol, Inst Theoret Comp Sci, CH-8092 Zurich, Switzerland

来源：

THEORETICAL COMPUTER SCIENCE | 2001年 / 268卷 / 01期

关键词：

on-line algorithms; analysis of algorithms; competitive analysis; list-update;

D O I：

10.1016/S0304-3975(00)00257-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The optimal competitive ratio for a randomized online list update algorithm is known to be at least 1.5 and at most 1.6, but the remaining gap is not yet closed. We present a new lower bound of 1.50084 for the partial cost model. The construction is based on game trees with incomplete information, which seem to be generally useful for the competitive analysis of online algorithms. (C) 2001 Elsevier Science B.V. All rights reserved.

引用

页码：3 / 16

页数：14

共 19 条

[1] A COMBINED BIT AND TIMESTAMP ALGORITHM FOR THE LIST UPDATE PROBLEM [J].