A Ramsey-type theorem for metric spaces and its applications for metrical task systems and related problems

Abstract

The paper gives a nearly logarithmic lower bound on the randomized competitive ratio for a Metrical Task Systems model (A. Borodin et al., 1992). This implies a similar lower bound for the extensively studied K-server problem. Our proof is based on proving a Ramsey-type theorem for metric spaces. In particular, we prove that in every metric space there exists a large subspace which is approximately a "hierarchically well-separated tree" (HST) (Y. Bartal, 1996). This theorem may be of independent interest.