An optimal on-line algorithm for metrical task system

摘要: In practice, almost all dynamic systems require decisions to be made on-line, without full knowledge of their future impact on the system. A general model for processing sequences tasks is introduced, and a on-line decision algorithm developed. It shown that, an important class special cases, this optimal among algorithms.Specifically, task system (S,d) consists set S states cost matrix d where d(i, j changing from state i (we assume that satisfies triangle inequality diagonal entries are 0). The given depends schedule sequence T1, T2,…, Tk s1, s2,…,sk si in which Ti processed; sum costs transition incurred.An scheduling one chooses only knowing T1T2…Ti. Such w-competitive if, any input sequence, its within additive constant w times offline cost. competitive ratio w(S, d) infimum there (S,d). = 2|S|–1 every symmetric, O(|S|2) Finally, randomized algorithms introduced. uniform (in d(i,j) 1 i,j), expected w¯(S,d) O(log|S|).