摘要: The k-server problem is perhaps the most influential online problem: natural, crisp, with a surprising technical depth that manifests richness of competitive analysis. conjecture, which was posed more than two decades ago when first studied within analysis framework, still open and has been major driving force for development area algorithms. This article surveys some results problem.
acm.org
elsevier.com
sci-hub.se 参考文章(72)
Gerhard J. Woeginger, Amos Fiat, Developments from a June 1996 seminar on Online algorithms: the state of the art ,(1998)
Elias Koutsoupias, Combinatorial optimization in congestion control ,(2000)
Online algorithms : The state of the art Lecture Notes in Computer Science. ,vol. 1442, ,(1998) , 10.1007/BFB0029561
Elias Koutsoupias, Christos Papadimitriou, Worst-case equilibria symposium on theoretical aspects of computer science. pp. 404- 413 ,(1999) , 10.1007/3-540-49116-3_38
Prabhakar Raghavan, Marc Snir, Memory Versus Randomization in On-line Algorithms (Extended Abstract) international colloquium on automata languages and programming. pp. 687- 703 ,(1989) , 10.1007/BFB0035792
Elias Koutsoupias, Christos Papadimitriou, Mihalis Yannakakis, Searching a Fixed Graph international colloquium on automata languages and programming. pp. 280- 289 ,(1996) , 10.1007/3-540-61440-0_135
Ran El-Yaniv, Allan Borodin, Online Computation and Competitive Analysis ,(1998)
René A. Sitters, Leen Stougie, Willem E. de Paepe, A competitive algorithm for the general 2-server problem international colloquium on automata languages and programming. pp. 624- 636 ,(2003) , 10.1007/3-540-45061-0_50
Xiaotie Deng, C. H. Papadimitriou, Competitive Distributed Decision-Making world computer congress on algorithms software architecture. ,vol. 16, pp. 350- 356 ,(1992) , 10.1007/BF01940643
Christos H. Papadimitriou, Computational Aspacts of Organization Theory (Extended Abstract) european symposium on algorithms. pp. 559- 564 ,(1996) , 10.1007/3-540-61680-2_82