The server problem and on-line games
Marek Chrobák, Lawrence L. Larmore · DIMACS series in discrete mathematics and theoretical computer science · 1992
2 The Server Problem 5 2.1 Convex Hulls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 The Equipoise Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2.1 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 The Work Function Algorithm for k Servers . . . . . . . . . . . . . . . . . . . . 17 2.3.1 A Conjectured Outline of the Proof of Optimality . . . . . . . . . . . . 20 2.3.2 WFA is 2-Competitive for 2 Servers . . . . . . . . . . . . . . . . . . . . 22