A strongly competitive randomized paging algorithm
From MaRDI portal
Publication:808246
DOI10.1007/BF01759073zbMath0731.68040OpenAlexW2083392624MaRDI QIDQ808246
Publication date: 1991
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01759073
Related Items (55)
Competitive randomized algorithms for nonuniform problems ⋮ Competitive \(k\)-server algorithms ⋮ Scheduling with resource management in manufacturing systems ⋮ Competitive algorithms for the weighted server problem ⋮ A better lower bound on the competitive ratio of the randomized 2-server problem ⋮ The working set algorithm has competitive ratio less than two ⋮ Uniform multipaging reduces to paging ⋮ Online companion caching ⋮ Combining request scheduling with web caching ⋮ Competitive caching of query results in search engines ⋮ The weighted 2-server problem ⋮ Randomized online multi-threaded paging ⋮ Improved integer linear programming formulations for the job sequencing and tool switching problem ⋮ On multi-threaded metrical task systems ⋮ Improved heuristic algorithms for the job sequencing and tool switching problem ⋮ Analysis of simple randomized buffer management for parallel I/O ⋮ General caching is hard: even with small pages ⋮ The relative worst-order ratio applied to paging ⋮ A proof of the optimality of the MIN paging algorithm using linear programming duality ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Paging with connections: FIFO strikes again ⋮ Paging more than one page ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ More on randomized on-line algorithms for caching. ⋮ Connection caching: Model and algorithms. ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Dynamic Balanced Graph Partitioning ⋮ Competitive clustering of stochastic communication patterns on a ring ⋮ 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 ⋮ Randomized on-line scheduling on two uniform machines ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ The worst page-replacement policy ⋮ Paging with request sets ⋮ Object Caching for Queries and Updates ⋮ New results on web caching with request reordering ⋮ Engineering Efficient Paging Algorithms ⋮ On competitive on-line paging with lookahead ⋮ Combinatorial optimization models for production scheduling in automated manufacturing systems ⋮ Paging more than one page ⋮ Competitive analysis of randomized paging algorithms ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ Scheduling multi-colour print jobs with sequence-dependent setup times ⋮ A randomized algorithm for two servers on the line. ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A general decomposition theorem for the \(k\)-server problem ⋮ \textsc{OnlineMin}: a fast strongly competitive randomized paging algorithm ⋮ On the power of randomization in on-line algorithms ⋮ A new measure for the study of on-line algorithms ⋮ Online file caching with rejection penalties ⋮ Trackless online algorithms for the server problem ⋮ Memoryless algorithms for the generalized k-server problem on uniform metrics
Cites Work
This page was built for publication: A strongly competitive randomized paging algorithm
