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

Simple item page
dc.creatorBartal, Yair
dc.creatorBollobas, Bela
dc.creatorMendel, Manor
dc.date2004-06-16
dc.date.accessioned2026-07-07T06:30:30Z
dc.date.available2026-07-07T06:30:30Z
dc.descriptionA 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.
dc.descriptionFix an error in the metadata. 31 pages, 0 figures. Preliminary version in FOCS '01. To be published in J. Comput. System Sci
dc.identifierhttps://arxiv.org/abs/cs/0406028
dc.identifierhttp://arxiv.org/abs/cs/0406028
dc.identifierJ. Comput. System Sci. 72(5):890-921, 2006
dc.identifierdoi:10.1016/j.jcss.2005.05.008
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/98356
dc.subjectData Structures and Algorithms
dc.titleRamsey-type theorems for metric spaces with applications to online problems
dc.typetext

Files

Collections

arXiv