On Decentralized Policies for the Stochastic k-Server Problem

In this paper we study a dynamic resource allocation problem which we call the stochastic k-server problem. In this problem, requests for some service to be performed appear at various locations over time, and we have a collection of k mobile servers which are capable of servicing these requests. When servicing a request, we incur a cost equal to the distance traveled by the dispatched server. The goal is to find a strategy for choosing which server to dispatch to each incoming request which keeps the average service cost as small as possible. In the model considered in this paper, the locations of service requests are drawn according to an IID random process. We show that, given a statistical description of this process, we can compute a simple decentralized state-feedback policy which achieves an average cost within a factor of two of the cost achieved by an optimal state-feedback policy. In addition, we demonstrate similar results for several extensions of the basic stochastic k-server problem.