Competitive algorithms for metrical service systems

possible requests, where each request r in R is a subset of M. An instance of
the system consists of an initial server position O and a sequence of requests
r_1,r_2,..., r_n. Every request r_t must be served immediately and irrevocably
by moving the server to a point x_t in r_t, before the future requests,
r_{t+1},r_{t+2}, ..., are given. The cost of the solution is the length of the
path in M followed by the server. In the on-line problem we do not allow the
algorithm to use any information on future requests, i.e., the choice of the
point x_t depends only on the system, the initial position O, and the requests
r_1,...,r_t. We say that an algorithm is c-competitive if the length of the path
constructed by the algorithm is at most c times the length of the optimal path.

Many on-line routing problems can be modeled as a metrical service system, e.g.
paging, layered graph traversal, and the k-server problem. We show a non-trivial
sufficient condition for finite competitiveness of any metrical service system
and provide an implicit algorithm. Our structural theorem gives new insight into
the competitive analysis of metrical service systems. Although our algorithm
attains huge competitive ratio's in general, it is the first provably
competitive algorithm for an elementary on-line routing problem: the general
two-server problem.