IEEE - Institute of Electrical and Electronics Engineers, Inc. - A decomposition theorem and bounds for randomized server problems

Author(s): Blum, A. ; Karloff, H. ; Rabani, Y. ; Saks, M.
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 January 1992
Conference Location: Pittsburgh, PA, USA
Conference Date: 24 October 1992
Page(s): 197 - 207
ISBN (Paper): 0-8186-2900-2
DOI: 10.1109/SFCS.1992.267772
Regular:

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... View More

Advertisement