Randomized competitive analysis for two server problems

DOI10.3390/A1010030MaRDI QIDQ1662430zbMATHOpenAlexFDO

Authors Kazuo Iwama, Jun Kawahara, 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

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

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)