Competitive algorithms for on-line problems
Mark S. Manasse, Lyle A. McGeoch, Daniel D. Sleator · 1988
An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. Examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. A competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.
Cited by 358 works. doi:10.1145/62212.62243
Authors
References
- Amortized efficiency of list update and paging rules
- Competitive snoopy caching
- An optimal online algorithm for metrical task systems
- Amortized analyses of self-organizing sequential search heuristics
- Sequencing Problems in Two-Server Systems
- Sequencing two servers on a sphere
- Algorithms for two graph problems: computing maximum-genus imbeddings and the two-server problem