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
מזהי עצם דיגיטלי (DOIs)	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

תקציר

הערה ביבליוגרפית

גישה למסמך

קבצים וקישורים אחרים

טביעת אצבע

פורמט ציטוט ביבליוגרפי