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

DOI10.1016/J.JCSS.2005.05.008zbMATH Open1094.68114OpenAlexW2007840228WikidataQ57318104 ScholiaQ57318104MaRDI QIDQ2496321FDOQ2496321

Authors: Béla Bollobás, Yair Bartal, Manor Mendel 

Publication date: 12 July 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2005.05.008

Recommendations

• scientific article; zbMATH DE number 1559591
• scientific article; zbMATH DE number 6469207
• A decomposition theorem for task systems and bounds for randomized server problems
• Randomized k-server algorithms for growth-rate bounded graphs
• scientific article; zbMATH DE number 1256655

zbMATH Keywords

metric Ramsey theorymetric task systemsonline servers problem

Mathematics Subject Classification ID

Randomized algorithms (68W20) Metric spaces, metrizability (54E35) Ramsey theory (05D10)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On the power of randomization in on-line algorithms
• Title not available (Why is that?)
• A tight bound on approximating arbitrary metrics by tree metrics
• Competitive snoopy caching
• Competitive analysis of randomized paging algorithms
• Competitive algorithms for server problems
• Competitive paging algorithms
• An optimal on-line algorithm for metrical task system
• A strongly competitive randomized paging algorithm
• On the k -server conjecture
• On Hilbertian subsets of finite metric spaces
• Title not available (Why is that?)
• Approximation algorithms for classification problems with pairwise relationships, metric labeling and Markov random fields
• Title not available (Why is that?)
• A general decomposition theorem for the \(k\)-server problem
• Better Algorithms for Unfair Metrical Task Systems and Applications
• Title not available (Why is that?)
• Randomized algorithms for metrical task systems
• A decomposition theorem for task systems and bounds for randomized server problems
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• Unfair problems and randomized algorithms for metrical task systems
• ON METRIC RAMSEY-TYPE DICHOTOMIES
• Limitations to Fréchet's metric embedding method
• Some low distortion metric Ramsey problems
• Title not available (Why is that?)

Cited In (18)

• Nested convex bodies are chaseable
• Online computation with advice
• Metrical task systems on trees via mirror descent and unfair gluing
• Embedding metrics into ultrametrics and graphs into spanning trees with constant average distortion
• Chasing convex bodies optimally
• Breaking the 2-competitiveness barrier for two servers in a tree
• Title not available (Why is that?)
• Ultrametric subsets with large Hausdorff dimension
• A new construction technique of a triangle-free 3-colored K16's
• Advances in metric embedding theory
• R-LINE: a better randomized 2-server algorithm on the line
• Asymptotic negative type properties of finite ultrametric spaces
• A note on restricted online Ramsey numbers of matchings
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• Randomized algorithm for the \(k\)-server problem on decomposable spaces
• Euclidean quotients of finite metric spaces
• An introduction to the Ribe program
• Quantitative geometry

This page was built for publication: Ramsey-type theorems for metric spaces with applications to online problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2496321)