An optimal online algorithm for metrical task systems
作者： A. Borodin , N. Linial , M. Saks
DOI: 10.1145/28395.28435
关键词:
摘要: 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 processing sequences tasks and develop online decision algorithm. show that, an important class special cases, this algorithm is optimal among algorithms.Specifically, task system (S, d) consists set S states cost matrix d where d(i, j) changing from state i j (we assume that satisfies triangle inequality diagonal entries are O.) The given depends A 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 operates within waste factor w if, any input sequence, its additive constant times offline cost. w(S, infirm d). = 2|S| - 1 every symmetric, O(|S|2)
acm.org
sci-hub.se 参考文章(11)
James Richard Bitner, Heuristics that dynamically alter data structures to reduce their access time. University of Illinois at Urbana-Champaign. ,(1976)
Matthew J. Sobel, Daniel P. Heyman, Stochastic models in operations research ,(1982)
Robert Endre Tarjan, Amortized Computational Complexity Siam Journal on Algebraic and Discrete Methods. ,vol. 6, pp. 306- 318 ,(1985) , 10.1137/0606031
F R Chung, D J Hajela, P D Seymour, Self-organizing sequential search and Hilbert's inequalities Proceedings of the seventeenth annual ACM symposium on Theory of computing - STOC '85. ,vol. 36, pp. 217- 223 ,(1985) , 10.1145/22145.22170
Ronald Rivest, On self-organizing sequential search heuristics Communications of the ACM. ,vol. 19, pp. 63- 67 ,(1976) , 10.1145/359997.360000
Y. C. Kan, S. M. Ross, OPTIMAL LIST ORDER UNDER PARTIAL MEMORY CONSTRAINTS Journal of Applied Probability. ,vol. 17, pp. 1004- 1015 ,(1980) , 10.1017/S0021900200097291
Daniel D. Sleator, Robert E. Tarjan, Amortized efficiency of list update and paging rules Communications of The ACM. ,vol. 28, pp. 202- 208 ,(1985) , 10.1145/2786.2793
James R. Bitner, Heuristics That Dynamically Organize Data Structures SIAM Journal on Computing. ,vol. 8, pp. 82- 110 ,(1979) , 10.1137/0208007
Anna R. Karlin, Mark S. Manasse, Larry Rudolph, Daniel D. Sleator, Competitive snoopy caching 27th Annual Symposium on Foundations of Computer Science (sfcs 1986). pp. 244- 254 ,(1986) , 10.1109/SFCS.1986.14
J. Ian Munro, Hendra Suwanda, Gaston H. Gonnet, Toward self-organizing linear search 20th Annual Symposium on Foundations of Computer Science (sfcs 1979). pp. 169- 174 ,(1979) , 10.1109/SFCS.1979.45