A Decomposition Theorem and Bounds for Randomized Server Problems

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 (/sup logk///sub loglogk/) for the server problem on k+1 equally-spaced points on a line, which corresponds to some natural motion-planning problems. >

Authors

• Avrim Blum
• Howard J. Karloff
• Yuval Rabani
• Michael E. Saks

Keywords

• Extraterrestrial measurements
• Computer science
• Cost function
• Game theory
• Motion-planning
• Postal services
• Mathematics
• Current measurement
• Motion measurement
• Upper bound
• Decomposition Theorem
• Left Side
• Lower Bound
• Non-negative
• Conjecture
• Proof Of Theorem
• Positive Integer
• Probe Sequences
• Random Strategy
• Pair Of Points
• Optimal Cost
• Round Trip
• Infimum
• Left Block
• Induction Step
• Uniform Spacing
• Moved To The Left
• Additive Constant
• Left Space