  In this paper, we study a stochastic variant of the celebrated k-server
problem. In the k-server problem, we are required to minimize the total
movement of k servers that are serving an online sequence of t requests in a
metric. In the stochastic setting we are given t independent distributions
<P_1, P_2,..., P_t> in advance, and at every time step i a request is drawn
from Pi. Designing the optimal online algorithm in such setting is NP-hard,
therefore the emphasis of our work is on designing an approximately optimal
online algorithm. We first show a structural characterization for a certain
class of non-adaptive online algorithms. We prove that in general metrics, the
best of such algorithms has a cost of no worse than three times that of the
optimal online algorithm. Next, we present an integer program that finds the
optimal algorithm of this class for any arbitrary metric. Finally, by rounding
the solution of the linear relaxation of this program, we present an online
algorithm for the stochastic k-server problem with the approximation factor of
3 in the line and circle metrics and O(log n) in a general metric of size n.
Moreover, we define the Uber problem, in which each demand consists of two
endpoints, a source and a destination. We show that given an a-approximation
algorithm for the k-server problem, we can obtain an (a+2)-approximation
algorithm for the Uber problem. Motivated by the fact that demands are usually
highly correlated with the time we study the stochastic Uber problem.
Furthermore, we extend our results to the correlated setting where the
probability of a request arriving at a certain point depends not only on the
time step but also on the previously arrived requests.
