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.