ملخص
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 |
| المعرِّفات الرقمية للأشياء | |
| حالة النشر | نُشِر - أغسطس 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).