Ramsey-type theorems for metric spaces with applications to online problems
From MaRDI portal
Publication:2496321
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
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)