Traversing Layered Graphs Using the Work Function Algorithm |
| |
Authors: | William R Burley |
| |
Institution: | Department of Computer Science and Engineering, 0114, University of California at San Diego, 9500 Gilman Drive, La Jolla, California, 92093-0114 |
| |
Abstract: | The work function algorithm (WFA) is an on-line algorithm that has been studied mostly in connection with thek-server problem, but can actually be used on a wide variety of on-line problems. Despite being a simple algorithm, WFA has proven to be difficult to analyze, and until recently few interesting results were known. We analyze the performance of the generalized work function algorithm, denoted α-WFA, for on-line traversal of layered graphs. We show that for layered graphs of widthkand any α>1, α-WFA achieves competitive ratio (α+1)(2α/(α−1))k−1−α. This gives anO(k2k)-competitive ratio for appropriate choice of α, improving the previous upper bound ofO(k32k). |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|