On-line problems are extremely common in computer science and operations research. For these problems an algorithm must be devised to decide how to respond to a request immediately when the request is made, without knowledge of future requests. Some familiar examples of on-line problems are: Controlling an elevator, controlling a disk drive, controlling caches, and data structures. An extremely powerful technique in the design and analysis of algorithms for on-line problems is that of amortization. In an amortized analysis, the cost of a sequence of requests is considered rather than the cost of each request individually. Algorithms efficient in the amortized sense balance the costs of expensive requests by inexpensive ones. A variety of new amortized-efficient algorithms and data structures have been devised. For many on-line problems there are on-line algorithms with amortized performance that is almost as good as the performance of any off-line algorithm on any sequence of requests. Such an on-line algorithm is said to be competitive. The PI is applying known techniques of amortization and competitiveness to a variety of other on-line problems, and developing new techniques for doing amortized analysis. The PI has been judged to be an outstanding computer scientist by the Presidential Young Investigator panel.
