תקציר
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.
| שפה מקורית | אנגלית |
|---|---|
| עמודים (מ-עד) | 890-921 |
| מספר עמודים | 32 |
| כתב עת | Journal of Computer and System Sciences |
| כרך | 72 |
| מספר גיליון | 5 |
| מזהי עצם דיגיטלי (DOIs) | |
| סטטוס פרסום | פורסם - אוג׳ 2006 |
| פורסם באופן חיצוני | כן |
הערה ביבליוגרפית
Funding Information:✩ A preliminary version, entitled “A Ramsey-type theorem for metric spaces and its applications for metrical task systems and related problems”, appeared in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001. * Corresponding author. E-mail addresses: [email protected] (Y. Bartal), [email protected] (B. Bollobás), [email protected], [email protected] (M. Mendel). 1 Supported in part by a grant from the Israeli Science Foundation (195/02). 2 Work mostly done while the author was a PhD student in Tel-Aviv University, under the supervision of Prof. A. Fiat. Author’s current address: Department of Computer Science, University of Illinois, Urbana, IL 61801, USA. Supported in part by a grant from the Israeli Science Foundation (195/02).