A randomized algorithm for two servers in cross polytope spaces

DOI10.1016/j.tcs.2010.08.022zbMath1206.68360OpenAlexW2132020364MaRDI QIDQ627107

Lawrence L. Larmore, James A. Oravec, Jun Kawahara, Kazuo Iwama, Wolfgang W. Bein

Publication date: 21 February 2011

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2010.08.022

zbMATH Keywords

online algorithmsrandomized algorithmscross polytope spaces

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, On the advice complexity of the \(k\)-server problem under sparse metrics, On Advice Complexity of the k-server Problem under Sparse Metrics

Cites Work

• Unnamed Item
• Unnamed Item
• A better lower bound on the competitive ratio of the randomized 2-server problem
• Knowledge state algorithms
• Competitive analysis of randomized paging algorithms
• A randomized algorithm for two servers on the line.
• An Optimal On-Line Algorithm for K Servers on Trees
• New Ressults on Server Problems
• Competitive algorithms for server problems
• Equitable Revisited
• KNOWLEDGE STATES FOR THE CACHING PROBLEM IN SHARED MEMORY MULTIPROCESSOR SYSTEMS
• On the k -server conjecture
• Beyond Competitive Analysis