Competitive analysis of randomized paging algorithms

DOI10.1016/S0304-3975(98)00116-9zbMath0944.68194MaRDI QIDQ1575677

Demetrios Achlioptas, Marek Chrobak, John Noga

Publication date: 21 August 2000

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

zbMATH Keywords

competitive analysisanalysis of algorithmson-line algorithmsrandomized algorithmspaging

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (35)

A better lower bound on the competitive ratio of the randomized 2-server problem ⋮ Randomized online computation with high probability guarantees ⋮ Online companion caching ⋮ The weighted 2-server problem ⋮ Measuring the problem-relevant information in input ⋮ General caching is hard: even with small pages ⋮ The relative worst-order ratio applied to paging ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Paging with connections: FIFO strikes again ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ More on randomized on-line algorithms for caching. ⋮ A randomized algorithm for two servers in cross polytope spaces ⋮ Unnamed Item ⋮ Dynamic Balanced Graph Partitioning ⋮ The \(k\)-server problem ⋮ Advice Complexity and Barely Random Algorithms ⋮ The optimal structure of algorithms for \(\alpha\)-paging ⋮ On the smoothness of paging algorithms ⋮ On Variants of File Caching ⋮ The \(k\)-resource problem in uniform metric spaces ⋮ Knowledge state algorithms ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ The worst page-replacement policy ⋮ Paging with request sets ⋮ A Randomized Algorithm for Two Servers in Cross Polytope Spaces ⋮ New results on web caching with request reordering ⋮ KNOWLEDGE STATES FOR THE CACHING PROBLEM IN SHARED MEMORY MULTIPROCESSOR SYSTEMS ⋮ Advice Complexity and Barely Random Algorithms ⋮ Engineering Efficient Paging Algorithms ⋮ An adaptive probabilistic algorithm for online \(k\)-center clustering ⋮ Unnamed Item ⋮ Unnamed Item ⋮ \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm ⋮ Online file caching with rejection penalties ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly competitive randomized paging algorithm
• Randomized algorithms for metrical task systems
• Competitive paging with locality of reference
• On the k-server conjecture
• An Optimal On-Line Algorithm for K Servers on Trees
• Competitive algorithms for server problems
• Competitive paging algorithms
• Competitive On-Line Algorithms for Distributed Data Management
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• Page Migration Algorithms Using Work Functions
• On the k -server conjecture

This page was built for publication: Competitive analysis of randomized paging algorithms