Ramsey-type theorems for metric spaces with applications to online problems
From MaRDI portal
Publication:2496321
DOI10.1016/j.jcss.2005.05.008zbMath1094.68114OpenAlexW2007840228WikidataQ57318104 ScholiaQ57318104MaRDI QIDQ2496321
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
Related Items
Asymptotic negative type properties of finite ultrametric spaces ⋮ A new construction technique of a triangle-free 3-colored K16's ⋮ R-LINE: a better randomized 2-server algorithm on the line ⋮ Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ An introduction to the Ribe program ⋮ Ultrametric subsets with large Hausdorff dimension ⋮ Advances in metric embedding theory ⋮ Nested convex bodies are chaseable ⋮ Quantitative geometry ⋮ Euclidean quotients of finite metric spaces ⋮ Online computation with advice ⋮ Metrical Task Systems on Trees via Mirror Descent and Unfair Gluing ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ Embedding Metrics into Ultrametrics and Graphs into Spanning Trees with Constant Average Distortion
Cites Work
- A strongly competitive randomized paging algorithm
- On Hilbertian subsets of finite metric spaces
- Competitive snoopy caching
- Randomized algorithms for metrical task systems
- Unfair problems and randomized algorithms for metrical task systems
- On the power of randomization in on-line algorithms
- Competitive analysis of randomized paging algorithms
- Some low distortion metric Ramsey problems
- A general decomposition theorem for the \(k\)-server problem
- Limitations to Fréchet's metric embedding method
- On metric Ramsey-type phenomena
- A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems
- Approximation algorithms for classification problems with pairwise relationships
- Competitive algorithms for server problems
- Competitive paging algorithms
- Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
- An optimal on-line algorithm for metrical task system
- On the k -server conjecture
- Better Algorithms for Unfair Metrical Task Systems and Applications
- ON METRIC RAMSEY-TYPE DICHOTOMIES
- A tight bound on approximating arbitrary metrics by tree metrics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Ramsey-type theorems for metric spaces with applications to online problems
