文章基本信息

标题：Measuring True Performance of the Work Function Algorithm for Solving the On-line k-Server Problem
本地全文：下载
作者：Rudec, Tomislav ; Baumgartner, Alfonzo ; Manger, Robert 等
期刊名称：Journal of Computing and Information Technology
印刷版ISSN：1330-1136
电子版ISSN：1846-3908
出版年度：2010
卷号：18
期号：4
页码：361-367
DOI：10.2498/cit.1001922
出版社：SRCE - Sveučilišni računski centar
摘要：This paper deals with the work function algorithm (WFA) for solving the on-line k-server problem. The paper is concerned with assessing actual performance of the WFA in terms of its serving costs. First, an efficient implementation of the WFA is briefly described. Next, some experiments are presented, where the performance of the implemented WFA has been measured on very large problem instances. Thereby, the problem instances have been selected from some frequently studied classes where sharp theoretical estimates of performance are available. Finally, the measured performance of the WFA is compared with the corresponding theoretical estimates and with some other algorithms.
关键词：on-line problems; on-line algorithms; k-server problem; work function algorithm (WFA); experiments