Ramsey-type theorems for metric spaces with applications to online problems
| Author(s) : | Manor Mendel B??la Bollob??s Yair Bartal, |
| Publisher : | N/A |
| Publication Date : | 2002 |
| ISSN : | N/A |
| Abstract : | 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 studied K-server problem. The proof is based on Ramsey-type theorems for metric spaces, that state that every metric space contains a large subspace which is approximately a hierarchically well-separated tree (and in particular an ultrametric). These Ramsey-type theorems may be of independent interest. 1, |