Randomized competitive analysis for two server problems

DOI10.3390/A1010030MaRDI QIDQ1662430zbMATH OpenOpenAlexFDO

Authors Kazuo Iwama, Jun Kawahara, Wolfgang W. Bein

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

online algorithmsrandomized algorithmsserver problems

Mathematics Subject Classification ID

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

Recommendations

• Randomized Competitive Analysis for Two-Server Problems
• scientific article; zbMATH DE number 2038743
• A better lower bound on the competitive ratio of the randomized 2-server problem
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• A randomized algorithm for two servers in cross polytope spaces
• scientific article; zbMATH DE number 1256655
• A competitive 2-server algorithm
• Competitive \(k\)-server algorithms
• Competitive algorithms for server problems
• Randomized algorithm for the \(k\)-server problem on decomposable spaces

Cites work

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

Cited in

(17)

• scientific article; zbMATH DE number 742965 (Why is no real title available?)
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• R-LINE: a better randomized 2-server algorithm on the line
• A better lower bound on the competitive ratio of the randomized 2-server problem
• Randomized online computation with high probability guarantees
• Breaking the 2-competitiveness barrier for two servers in a tree
• Randomized Competitive Analysis for Two-Server Problems
• scientific article; zbMATH DE number 2038743 (Why is no real title available?)
• R-LINE: a better randomized 2-server algorithm on the line
• Competitive randomized algorithms for nonuniform problems
• Server problems and resistive spaces
• Multiple spin-block decisions
• Randomized algorithms for online bounded bidding
• A competitive 2-server algorithm
• The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem
• A randomized algorithm for two servers on the line.
• A randomized algorithm for two servers in cross polytope spaces

This page was built for publication: Randomized competitive analysis for two server problems

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