A decomposition theorem and bounds for randomized server problems

Avrim Blum, Howard Karloff, Yuval Rabani, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

25 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
PublisherIEEE Computer Society
Pages197-207
Number of pages11
ISBN (Electronic)0818629002
DOIs
StatePublished - 1992
Externally publishedYes
Event33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 - Pittsburgh, United States
Duration: Oct 24 1992Oct 27 1992

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1992-October
ISSN (Print)0272-5428

Conference

Conference33rd Annual Symposium on Foundations of Computer Science, FOCS 1992
Country/TerritoryUnited States
CityPittsburgh
Period10/24/9210/27/92

All Science Journal Classification (ASJC) codes

  • General Computer Science

Fingerprint

Dive into the research topics of 'A decomposition theorem and bounds for randomized server problems'. Together they form a unique fingerprint.

Cite this