An optimal online algorithm for metrical task systems
Allan Borodin, Nathan Linial, Michael Saks · 1987
In practice, almost all dynamic systems require decisions to be made online, without full knowledge of their future impact on the system. We introduce a general model for the processing of sequences of tasks and develop a general online decision algorithm. We show that, for an important class of special cases, this algorithm is optimal among all online algorithms.
Cited by 164 works. doi:10.1145/28395.28435
Authors
References
- Amortized efficiency of list update and paging rules
- Stochastic models in operations research
- On self-organizing sequential search heuristics
- Amortized Computational Complexity
- Heuristics That Dynamically Organize Data Structures
- Amortized analyses of self-organizing sequential search heuristics
- Optimal list order under partial memory constraints
- Competitive snoopy caching
- Heuristics that dynamically alter data structures to reduce their access time.
- Toward self-organizing linear search