On-line algorithms work with only partial information about the input data. At each time step, such an algorithm receives one unit of data, and has to produce partial results before seeing the remaining data. This project will focus on on-line competitive algorithms, which are algorithms that return a solution that is not worse than a constant times the optimal one. In the k-server problem, an on-line sequence of requests must each be met by one of k servers which move around in a metric space. The cost of a server algorithm is defined to be the total movement of the servers. General methods for solving on-line problems will be formulated in terms of on-line games. The techniques developed in this work should find applications in other on-line problems.
