Competitive paging algorithms
From MaRDI portal
Publication:3988829
DOI10.1016/0196-6774(91)90041-VzbMath0753.68018OpenAlexW2054033098MaRDI QIDQ3988829
No author found.
Publication date: 28 June 1992
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(91)90041-v
Parallel algorithms in computer science (68W10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Theory of operating systems (68N25)
Related Items
Competitive randomized algorithms for nonuniform problems ⋮ Competitive \(k\)-server algorithms ⋮ Competitive algorithms for the weighted server problem ⋮ The working set algorithm has competitive ratio less than two ⋮ Uniform multipaging reduces to paging ⋮ Randomized online computation with high probability guarantees ⋮ Online companion caching ⋮ Combining request scheduling with web caching ⋮ Competitive caching of query results in search engines ⋮ Randomized online multi-threaded paging ⋮ Page migration with limited local memory capacity ⋮ A universal online caching algorithm based on pattern matching ⋮ Serving Online Requests with Mobile Servers ⋮ Mechanisms with Monitoring for Truthful RAM Allocation ⋮ Analysis of simple randomized buffer management for parallel I/O ⋮ Randomized competitive analysis for two server problems ⋮ The work function algorithm for the paging 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 proof of the optimality of the MIN paging algorithm using linear programming duality ⋮ Caching with Time Windows and Delays ⋮ A primal-dual online algorithm for the \(k\)-server problem on weighted HSTs ⋮ Paging with connections: FIFO strikes again ⋮ Paging more than one page ⋮ Breaking the 2-competitiveness barrier for two servers in a tree ⋮ Competitive Algorithms for Generalized k -Server in Uniform Metrics ⋮ Online Metric Algorithms with Untrusted Predictions ⋮ More on randomized on-line algorithms for caching. ⋮ Expected linear round synchronization: the missing link for linear Byzantine SMR ⋮ Connection caching: Model and algorithms. ⋮ Greedy \(\varDelta \)-approximation algorithm for covering with arbitrary constraints and submodular cost ⋮ Comparison and analysis of ten static heuristics-based Internet data replication techniques ⋮ Unnamed Item ⋮ Online metric tracking and smoothing ⋮ Competitive strategy for on-line leasing of depreciable equipment ⋮ Dynamic Balanced Graph Partitioning ⋮ The \(k\)-server problem ⋮ Competitive clustering of stochastic communication patterns on a ring ⋮ Randomized Competitive Analysis for Two-Server Problems ⋮ On the smoothness of paging algorithms ⋮ On Variants of File Caching ⋮ The k-Server Problem with Delays on the Uniform Metric Space ⋮ Parametrized Metrical Task Systems ⋮ Unnamed Item ⋮ Online algorithms with advice: the tape model ⋮ The \(k\)-resource problem in uniform metric spaces ⋮ The weighted list update problem and the lazy adversary ⋮ Knowledge state algorithms ⋮ Ramsey-type theorems for metric spaces with applications to online problems ⋮ The worst page-replacement policy ⋮ Paging with request sets ⋮ Unnamed Item ⋮ New results on web caching with request reordering ⋮ On Certain New Models for Paging with Locality of Reference ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Managing multiple mobile resources ⋮ Online \(k\)-taxi via double coverage and time-reverse primal-dual ⋮ Engineering Efficient Paging Algorithms ⋮ On competitive on-line paging with lookahead ⋮ Paging more than one page ⋮ Graphs and Algorithms in Communication Networks on Seven League Boots ⋮ On the competitiveness of the move-to-front rule ⋮ Competitive analysis of randomized paging algorithms ⋮ Competitive Algorithms for Layered Graph Traversal ⋮ Randomized algorithm for the \(k\)-server problem on decomposable spaces ⋮ Paging against a distribution and IP networking ⋮ On randomization in on-line computation. ⋮ 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 ⋮ Randomized competitive algorithms for the list update problem ⋮ Online file caching with rejection penalties ⋮ Parameterized analysis of paging and list update algorithms ⋮ A strongly competitive randomized paging algorithm ⋮ Trackless online algorithms for the server problem
