Uniform Service Systems with k Servers

摘要

We consider the porblem of k servers situated on a uniform metric space that must serve a equence of requests, where each request consists of a set of locations of the metric space and can be served by moving a server to any of the nodes of the set. The goal is to minimize the total distance taveled by the servers. This problem genralizes a problem presented by Chrobak and Larmore in [7]. We give lower and upper bounds on the compertitive ratio achievable by on-line algorithms for this problem, and consider also interesting particular cases.