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

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

2004-06-16

arxiv.org/abs/cs/0406028v1

J. Comput. System Sci. 72(5):890-921, 2006

Computer Science

Data Structures and Algorithms

Fix an error in the metadata. 31 pages, 0 figures. Preliminary version in FOCS '01. To be published in J. Comput. System Sci

Scientific paper

10.1016/j.jcss.2005.05.008

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.

Affiliated with

Also associated with

No associations

Rating

Ramsey-type theorems for metric spaces with applications to online problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Ramsey-type theorems for metric spaces with applications to online problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Ramsey-type theorems for metric spaces with applications to online problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-178049