The On-Line K-Server Problem
A. Floratos, Ravi B. Boppana · 1997
We survey the research performed during the last few years on the on-line k-server problem over metric spaces. A variety of algorithms are presented --- both deterministic and randomized --- and their performance is studied in the framework of competitive analysis. Restrictions of the problem to special cases of metric spaces are also considered. 1 Introduction In much of the theory of algorithm analysis the following fundamental assumption is made: whenever an algorithm is called upon to solve any particular instance of a problem, all the input necessary for the solution is available at the time the algorithm begins its computation. There are situations, though, where this assumption is just not realistic. In many cases the nature of a problem dictates that the input has to be presented to the algorithm incrementally, one piece at a time, and the algorithm must produce a corresponding piece of output based only on what has been seen up to that point. The optimal response though,...