Randomized competitive analysis for two server problems

DOI10.3390/a1010030zbMath1445.68339OpenAlexW1967323656MaRDI QIDQ1662430

Jun Kawahara, Kazuo Iwama, Wolfgang W. Bein

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a1010030

zbMATH Keywords

online algorithmsrandomized algorithmsserver problems

Mathematics Subject Classification ID

Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Related Items

R-LINE: a better randomized 2-server algorithm on the line ⋮ Breaking the 2-competitiveness barrier for two servers in a tree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A better lower bound on the competitive ratio of the randomized 2-server problem
• Randomized competitive algorithms for the list update problem
• Competitive randomized algorithms for nonuniform problems
• A randomized algorithm for two servers on the line.
• Random walks on weighted graphs and applications to on-line algorithms
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• On the online bin packing problem
• Competitive algorithms for server problems
• Equitable Revisited
• Competitive paging algorithms
• On the k -server conjecture
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Gadgets, Approximation, and Linear Programming
• Dynamic TCP acknowledgement and other stories about e/(e-1)
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• Finite-State Online Algorithms and Their Automated Competitive Analysis