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.

Agency
National Science Foundation (NSF)
Institute
Division of Computer and Communication Foundations (CCF)
Application #
8658139
Program Officer
Dana S. Richards
Project Start
Project End
Budget Start
1987-08-01
Budget End
1993-01-31
Support Year
Fiscal Year
1986
Total Cost
$312,000
Indirect Cost
Name
Carnegie-Mellon University
Department
Type
DUNS #
City
Pittsburgh
State
PA
Country
United States
Zip Code
15213