This research concerns on-line algorithms and is focused on two problems, generalizing well-known open problems. The first is: the given any on-line algorithm and any specific kind of restriction on computational power memory or information flow, does there exist, an on-line algorithm that satisfies this restriction and is still optimal (among all on-line algorithms)? The second is the question whether randomization helps for the 2-server problem.
In particular, the project introduces a new restriction on information flow for on-line algorithms called tracklessness and seeks to answer the above questions for trackless on-line algorithms.
Some effort will also be expended on the major problem of the area, the k-server conjecture.
Besides the server problem, the research will attempt to settle a number of other on-line problems for which optimal competitiveness is unknown, including: randomized list update, multiprocessor scheduling, and page migration.
A number of tools developed by the PI (in conjunction with Chrobak) have been used successfully, by them and by others, including workfunctions, pseudocost, competitive games, and convex hulls. Computer simulations are an essential tool in the research. A major component of the work in finding additional generic tools for classes of problems.
