A competitive algorithm for the general 2-server problem
作者： René A. Sitters , Leen Stougie , Willem E. de Paepe
关键词:
摘要: We consider the general on-line two server problem in which at each step both servers receive a request, is point metric space. One of has to be moved its request. The special case where requests are points on real line known as CNN-problem. It been well-known open question if an algorithm with constant competitive ratio exists for this problem. answer affirmative sense by providing first two-server any
springer.com
tue.nl 
core.ac.uk 参考文章(8)
Marek Chrobak, Jiří Sgall, The Weighted 2-Server Problem symposium on theoretical aspects of computer science. pp. 593- 604 ,(2000) , 10.1007/3-540-46541-3_49
Elias Koutsoupias, David Scot Taylor, The CNN Problem and Other k-Server Variants symposium on theoretical aspects of computer science. pp. 581- 592 ,(2000) , 10.1007/3-540-46541-3_48
Elias Koutsoupias, Christos H. Papadimitriou, On the k-server conjecture Journal of the ACM. ,vol. 42, pp. 971- 983 ,(1995) , 10.1145/210118.210128
Mark S Manasse, Lyle A McGeoch, Daniel D Sleator, Competitive algorithms for server problems Journal of Algorithms. ,vol. 11, pp. 208- 230 ,(1990) , 10.1016/0196-6774(90)90003-W
Marek Chrobak, Lawrence L. Larmore, An optimal on-line algorithm for K-servers on trees SIAM Journal on Computing. ,vol. 20, pp. 144- 148 ,(1991) , 10.1137/0220008
M. Chrobak, H. Karloof, T. Payne, S. Vishwnathan, New results on server problems SIAM Journal on Discrete Mathematics. ,vol. 4, pp. 172- 181 ,(1991) , 10.1137/0404017
Allan Borodin, Nathan Linial, Michael E. Saks, An optimal on-line algorithm for metrical task system Journal of the ACM. ,vol. 39, pp. 745- 763 ,(1992) , 10.1145/146585.146588
Amos Fiat, Moty Ricklin, Competitive algorithms for the weighted server problem Theoretical Computer Science. ,vol. 130, pp. 85- 99 ,(1994) , 10.1016/0304-3975(94)90154-6