摘要: During the last 15 years online algorithms have received considerable research interest. In this survey we give an introduction to competitive analysis of and present important results. We study interesting application areas identify open problems.
springer.com
sci-hub.se 参考文章(87)
Y. Azai, L. Epstein, On-line load balancing of temporary tasks on identical machines Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems. pp. 119- 125 ,(1997) , 10.1109/ISTCS.1997.595163
A. Fiat, M. Mendel, Truly online paging with locality of reference foundations of computer science. pp. 326- 335 ,(1997) , 10.1109/SFCS.1997.646121
Elias Koutsoupias, Christos H. Papadimitriou, Beyond Competitive Analysis SIAM Journal on Computing. ,vol. 30, pp. 300- 317 ,(2000) , 10.1137/S0097539796299540
Yair Bartal, Avrim Blum, Carl Burch, Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems symposium on the theory of computing. pp. 711- 719 ,(1997) , 10.1145/258533.258667
D. J. Wheeler, M. Burrows, A Block-sorting Lossless Data Compression Algorithm ,(1994)
Hal A. Kierstead, Coloring Graphs On-line Lecture Notes in Computer Science. pp. 281- 305 ,(1998) , 10.1007/BFB0029574
JiŘí Sgall, On-line Scheduling Lecture Notes in Computer Science. pp. 196- 231 ,(1998) , 10.1007/BFB0029570
Yossi Azar, On-line Load Balancing Lecture Notes in Computer Science. pp. 178- 195 ,(1998)
Edith Cohen, Haim Kaplan, Uri Zwick, Connection caching Proceedings of the thirty-first annual ACM symposium on Theory of computing - STOC '99. pp. 612- 621 ,(1999) , 10.1145/301250.301416
Kim S Larsen, Jens S Frederiksen, None, Packet Bundling scandinavian workshop on algorithm theory. pp. 328- 337 ,(2002)