An online problem is one in which an algorithm must handle a sequence of requests, processing each request without knowledge of the future requests. Online problems are encountered frequently in computer science. They are especially common in computer systems and data structures. The standard method for evaluating an online algorithm is called competitive analysis. This project has three parts. The first is to investigate specific online problems, principally from the competitive viewpoint. These problems include some well studied problems that have remained open and some new problems identified in this proposal. The second is to understand the role of randomness, especially in finding simpler or more efficient algorithms. Finally, it has been observed that in several applications, algorithms designed to be competitive are out- performed by other, equally competitive, and sometimes non- competitive, algorithms. To explain this behavior, the third part of this project is to find a new metric for the evaluation of online algorithms. Such a metric is likely to be a refinement of competitive analysis.
