Trackless online algorithms for the server problem

被引：8

作者：

Bein, WW ^{[1
]}

Larmore, LL ^{[1
]}

机构：

[1] Univ Nevada, Dept Comp Sci, Las Vegas, NV 89154 USA

来源：

INFORMATION PROCESSING LETTERS | 2000年 / 74卷 / 1-2期

基金：

美国国家科学基金会;

关键词：

design of algorithms; online algorithms; randomized algorithms; competitive analysis; k-server problem; paging;

D O I：

10.1016/S0020-0190(00)00034-X

中图分类号：

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

学科分类号：

0812 ;

摘要：

A class of "simple" online algorithms for the k-server problem is identified. This class, for which the term trackless is introduced, includes many known server algorithms. The k-server conjecture fails for trackless algorithms. A lower bound of 23/11 on the competitiveness of any deterministic trackless 2-server algorithm and a lower bound of 1 + root 2/2 on the competitiveness of any randomized trackless 2-server problem are given. (C) 2000 Published by Elsevier Science B.V. An rights reserved.

引用

页码：73 / 79

页数：7

共 15 条

[1]

ACHLIOPTAS D, 1996, LECT NOTES COMPUTER, V1136, P419

[2] COMPETITIVE PAGING WITH LOCALITY OF REFERENCE [J].