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

DOI10.1016/J.JCSS.2005.05.008MaRDI QIDQ2496321zbMATHOpenAlexWikidataFDO

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

zbMATH Keywords

metric Ramsey theorymetric task systemsonline servers problem

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(18)

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

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)