The Randomized k-Server Conjecture Is False!

We prove a few new lower bounds on the randomized competitive ratio for the k -server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987).

Authors

• Sébastien Bubeck
• Christian Coester
• Yuval Rabani

Keywords

• $k$-server
• competitive analysis
• lower bounds
• metrical task systems
• online computing
• randomized algorithms