M. S. Manasse, L. A. McGeoch, D. D. Sleator, Competitive Algorithms for Server Problems, Journal of Algorithms 11, 208-230 (1990)

Thek-serverproblem is that of planning the motion ofkmobile servers on the vertices of a graph under a sequence of requests for service. Each request consists of the name of a vertex, and is satisfied by placing a server at the requested vertex. The requests must be satisfied in their order of occurrence. The cost of satisfying a

sequence of requests is the distance moved by the servers. In this paper we study on-line algorithms for this problem from thecompetitivepoint of view. That is, we seek to develop on-line algorithms whose performance on any sequence of requests is as close as possible to the performance of the optimum off-line algorithm. We

obtain optimally competitive algorithms for several important cases. Because of the flexibility in choosing the distances in the graph and the number of servers, thek-server problem can be used to model a number of important paging and caching problems. It can also be used as a building block for solving more general problems. We show how server algorithms can be used to solve a seemingly more general class

of problems known astask systems.

Daniel Sleator: Email, Home Page, Papers

Last modified: Sat Jan 21 07:15:44 EST 2006