Competitive algorithms for server problems

摘要: Abstract The k-server problem is that of planning the motion k mobile servers on vertices a graph under sequence requests for service. Each request consists name vertex, and satisfied by placing server at requested vertex. must be in their order occurrence. cost satisfying distance moved servers. In this paper we study on-line algorithms from competitive point view. That is, seek to develop whose performance any as close possible optimum off-line algorithm. We obtain optimally several important cases. Because flexibility choosing distances number servers, can used model paging caching problems. It also building block solving more general show how solve seemingly class problems known task systems.