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.

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

References in corpus (6)

• Competitive Paging Algorithms
• On metric Ramsey-type phenomena
• On some low distortion metric Ramsey problems
• Better algorithms for unfair metrical task systems and applications
• Limitations to Frechet's Metric Embedding Method
• On Metric Ramsey-type Dichotomies

Cited by in corpus (12)

• Euclidean quotients of finite metric spaces
• Ultrametric subsets with large Hausdorff dimension
• Advances in Metric Ramsey Theory and its Applications
• An introduction to the Ribe program
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Clan Embeddings into Trees, and Low Treewidth Graphs
• A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics
• Slaying Hydrae: Improved Bounds for Generalized k-Server in Uniform Metrics
• Competitive ratio versus regret minimization: achieving the best of both worlds
• Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
• The asymptotic enhanced negative type of finite ultrametric spaces
• Nonlinear Dimension Reduction via Outer Bi-Lipschitz Extensions