  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.
