Randomized Competitive Analysis for Two-Server Problems

DOI10.1007/978-3-540-87744-8_14MaRDI QIDQ3541083zbMATH OpenOpenAlexFDO

Authors Jun Kawahara, Wolfgang W. Bein, Kazuo Iwama

Publication date 25 November 2008

Published in Algorithms - ESA 2008 (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• Randomized competitive analysis for two server problems
• A randomized algorithm for two servers on the line.
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• scientific article; zbMATH DE number 1003270
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms

Cites work

• A better lower bound on the competitive ratio of the randomized 2-server problem
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive algorithms for server problems
• Competitive paging algorithms
• Dynamic TCP acknowledgement and other stories about e/(e-1)
• Equitable Revisited
• Every planar map is four colorable. I: Discharging
• Finite-State Online Algorithms and Their Automated Competitive Analysis
• Gadgets, Approximation, and Linear Programming
• scientific article; zbMATH DE number 1003270 (Why is no real title available?)
• scientific article; zbMATH DE number 65695 (Why is no real title available?)
• 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
• Randomized competitive algorithms for the list update problem

Cited in

(18)

• A competitive 2-server algorithm
• Competitive randomized algorithms for nonuniform problems
• Randomized competitive analysis for two server problems
• A randomized algorithm for two servers on the line.
• The weighted 2-server problem
• Randomized online computation with high probability guarantees
• A decomposition theorem for task systems and bounds for randomized server problems
• 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
• Lower Bounds for Randomized k-Server and Motion-Planning Algorithms
• scientific article; zbMATH DE number 1962818 (Why is no real title available?)
• scientific article; zbMATH DE number 2038743 (Why is no real title available?)
• scientific article; zbMATH DE number 742965 (Why is no real title available?)
• A Randomized Algorithm for Two Servers in Cross Polytope Spaces
• A randomized algorithm for two servers in cross polytope spaces
• Server problems and resistive spaces
• Randomized algorithms for online bounded bidding
• R-LINE: a better randomized 2-server algorithm on the line

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 Q3541083)