A network flow implementation of a modified work function algorithm for solving the k-server problem

被引：0

作者：

Baumgartner, Alfonzo ^{[1
]}

Manger, Robert ^{[2
]}

Hocenski, Zeljko ^{[3
]}

机构：

[1] Univ Osijek, Fac Elect Engn, Kneza Trpimira 2b, Osijek 31000, Croatia

[2] Univ Zagreb, Dept Math, Zagreb 10000, Croatia

[3] Univ Osijek, Fac Elect Engn, Osijek 31000, Croatia

来源：

SOR'07: PROCEEDINGS OF THE 9TH INTERNATIONAL SYMPOSIUM ON OPERATIONAL RESEARCH IN SLOVENIA | 2007年

关键词：

on-line problems; on-line algorithms; the k-server problem; the work function algorithm (WFA); moving windows; implementation; network flows; computational complexity;

D O I：

暂无

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We study a modification of the well known work function algorithm (WFA) for solving the on-line k-server problem. Our modified WFA is based on a moving window, i.e. on the approximate work function that takes into account only a fixed number of most recent on-line requests. In this paper we describe in detail a network flow implementation of the modified WFA. We also present theoretical estimates and experimental measurements dealing with the computational complexity of the implemented algorithm.

引用

页码：83 / +

页数：2

共 11 条

[1] [Anonymous], 2004, LINEAR PROGRAMMING N
[2] On the competitive ratio of the work function algorithm for the k-server problem
Bartal, Y
Koutsoupias, E
[J]. THEORETICAL COMPUTER SCIENCE, 2004, 324 (2-3) : 337 - 345
[3] BAUMGARTNER A, 2007, P 29 C INF TECHN INT
[4] NEW RESULTS ON SERVER PROBLEMS
CHROBAK, M
KARLOFF, H
PAYNE, T
VISHWANATHAN, S
[J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1991, 4 (02) : 172 - 181
[5] IRANI S, 1997, APPROXIMATION ALGORI, P521
[6] Jungnickel D., 2005, Graphs, Networks and Algorithms
[7] Koutsoupias E., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P507, DOI 10.1145/195058.195245
[8] COMPETITIVE ALGORITHMS FOR SERVER PROBLEMS
MANASSE, MS
MCGEOCH, LA
SLEATOR, DD
[J]. JOURNAL OF ALGORITHMS, 1990, 11 (02) : 208 - 230
[9] Quinn M.J., 2003, Parallel Programming in C with MPI and OpenMP
[10] RUDEC T, 2001, THESIS U ZABREB

← 1 2 →