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

Yair Bartal; Béla Bollobás; Manor Mendel

doi:10.1016/j.jcss.2005.05.008

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

Yair Bartal
, Béla Bollobás
, 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 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
المعرِّفات الرقمية للأشياء	https://doi.org/10.1016/j.jcss.2005.05.008
حالة النشر	نُشِر - أغسطس 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).

الوصول إلى المستند

10.1016/j.jcss.2005.05.008

الملفات والروابط الأخرى

Link to publication in Scopus

قم بذكر هذا

@article{bd56c577e96e4430ac89c58fe53c5691,

title = "Ramsey-type theorems for metric spaces with applications to online problems",

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.",

keywords = "Metric Ramsey theory, Metric task systems, Online servers problem",

author = "Yair Bartal and B{\'e}la Bollob{\'a}s and Manor Mendel",

note = "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{\'a}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{\textquoteright}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).",

year = "2006",

month = aug,

doi = "10.1016/j.jcss.2005.05.008",

language = "אנגלית",

volume = "72",

pages = "890--921",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "5",

}

TY - JOUR

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

AU - Bartal, Yair

AU - Bollobás, Béla

AU - Mendel, Manor

N1 - 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).

PY - 2006/8

Y1 - 2006/8

N2 - 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.

AB - 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.

KW - Metric Ramsey theory

KW - Metric task systems

KW - Online servers problem

UR - https://www.scopus.com/pages/publications/33646531395

U2 - 10.1016/j.jcss.2005.05.008

DO - 10.1016/j.jcss.2005.05.008

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:33646531395

SN - 0022-0000

VL - 72

SP - 890

EP - 921

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 5

ER -

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

ملخص

ملاحظة ببليوغرافية

الوصول إلى المستند

الملفات والروابط الأخرى

بصمة

قم بذكر هذا