This project focuses on a number of topics related to on-line problems. 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. On-line competitive algorithms are algorithms which return a solution that is not worse than a constant times the optimal one. One of the goals is to solve the k-server problem. An optimal algorithm for k servers has already been developed: the algorithm is 2-competitive for two servers. A closed form function, which is a good candidate for the potential function for k = 3, is examined. A second goal is to attack a number of other on-line problems for which optimal competitiveness is unknown, including: randomized list update, multi-processor scheduling, and page migration; and to develop a general theory of on-line problem solutions. A third goal is to show how the techniques, developed for the solution of the k-server problem, can be applied to other on-line problems. In particular, applications of work functions, forgiveness and stable distributions to general on-line problems are developed. Note: This is a companion award to CCR-9503498 (PI: Chrobak) of University of California, Riverside.
