The dynamic servers problem

摘要

We present a generalization of the k-server problem, called dynamic servers, where the number of servers is not fixed a priori; rather, the algorithm is free to increase and decrease the number of servers at will, but it is required to pay a rental cost for each active server at designated times. This new problem is a simultaneous abstraction for problems arising in a variety of applications, particularly the information delivery problem for video-on-demand, web server management, and the problem of dynamic maintenance of kinematic structures for applications in molecular biology, simulation of hyperredundant robots, collision detection, and computer animation. The problem also appears to be of theoretical significance as a natural new paradigm in the realm of online algorithms. We give approximation algorithms for the offline problem, and initiate the study of the online version of this problem. We present an O(minflog n; log aeg)-competitive algorithm where n is the number of reques...