AN OPTIMAL ONLINE ALGORITHM FOR K-SERVERS ON TREES

被引：97

作者：

CHROBAK, M

LARMORE, LL

机构：

[1] Univ of California, Riverside, CA

来源：

SIAM JOURNAL ON COMPUTING | 1991年 / 20卷 / 01期

关键词：

ONLINE ALGORITHMS; THE SERVER PROBLEM; COMPETITIVE ANALYSIS; METRIC SPACES; TREES;

D O I：

10.1137/0220008

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The k-server problem is investigated when the metric space is a tree. For this case an on-line k-competitive algorithm for k-servers is presented. The competitiveness ratio k is optimal. The algorithm is memoryless, in the sense that it does not use any information from the past.

引用

页码：144 / 148

页数：5