On-line algorithms for the K-server problem and its variants.

by Chi-ming Wat.Thesis (M.Phil.)--Chinese University of Hong Kong, 1995.Includes bibliographical references (leaves 77-82).Chapter 1 --- Introduction --- p.1Chapter 1.1 --- Performance analysis of on-line algorithms --- p.2Chapter 1.2 --- Randomized algorithms --- p.4Chapter 1.3 --- Types of adversaries --- p.5Chapter 1.4 --- Overview of the results --- p.6Chapter 2 --- The k-server problem --- p.8Chapter 2.1 --- Introduction --- p.8Chapter 2.2 --- Related Work --- p.9Chapter 2.3 --- The Evolution of Work Function Algorithm --- p.12Chapter 2.4 --- Definitions --- p.16Chapter 2.5 --- The Work Function Algorithm --- p.18Chapter 2.6 --- The Competitive Analysis --- p.20Chapter 3 --- The weighted k-server problem --- p.27Chapter 3.1 --- Introduction --- p.27Chapter 3.2 --- Related Work --- p.29Chapter 3.3 --- Fiat and Ricklin's Algorithm --- p.29Chapter 3.4 --- The Work Function Algorithm --- p.32Chapter 3.5 --- The Competitive Analysis --- p.35Chapter 4 --- The Influence of Lookahead --- p.41Chapter 4.1 --- Introduction --- p.41Chapter 4.2 --- Related Work --- p.42Chapter 4.3 --- The Role of l-lookahead --- p.43Chapter 4.4 --- The LRU Algorithm with l-lookahead --- p.45Chapter 4.5 --- The Competitive Analysis --- p.45Chapter 5 --- Space Complexity --- p.57Chapter 5.1 --- Introduction --- p.57Chapter 5.2 --- Related Work --- p.59Chapter 5.3 --- Preliminaries --- p.59Chapter 5.4 --- The TWO Algorithm --- p.60Chapter 5.5 --- Competitive Analysis --- p.61Chapter 5.6 --- Remarks --- p.69Chapter 6 --- Conclusions --- p.70Chapter 6.1 --- Summary of Our Results --- p.70Chapter 6.2 --- Recent Results --- p.71Chapter 6.2.1 --- The Adversary Models --- p.71Chapter 6.2.2 --- On-line Performance-Improvement Algorithms --- p.73Chapter A --- Proof of Lemma1 --- p.75Bibliography --- p.7