@inproceedings{647ec2d934364e45ab542aec5814c1ae,

title = "A decomposition theorem and bounds for randomized server problems",

abstract = "The authors prove a lower bound of Omega ( square root logk/loglogk) for the competitive ratio of randomized algorithms for the k-server problem against an oblivious adversary. The bound holds for arbitrary metric spaces (of at least k+1 points) and provides a new lower bound for the metrical task system problem as well. This improves the previous best lower bound of Omega (loglogk) for arbitrary metric spaces, more closely approaching the conjectured lower bound of Omega (logk). They also prove a lower bound of Omega (logk/loglogk) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems.",

author = "Avrim Blum and Howard Karloff and Yuval Rabani and Michael Saks",

note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 ; Conference date: 24-10-1992 Through 27-10-1992",

year = "1992",

doi = "10.1109/SFCS.1992.267772",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "197--207",

booktitle = "Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992",

address = "United States",

}