Ramsey-type theorems for metric spaces with applications to online problems

Yair Bartal, Bela Bollobas, Manor Mendel

A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively stud…