Competitive paging algorithms
Journal of AlgorithmsPublished 1 December 1991Open access
Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel D. Sleator, Neal E. Young
Citations455
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
The marking algorithm is developed, a randomized on-line algorithm for the paging problem, which it is proved that its expected cost on any sequence of requests is within a factor of 2Hk of optimum.
Abstract
The paging problem is that of deciding which pages to keep in a memory of k\npages in order to minimize the number of page faults. This paper introduces the\nmarking algorithm, a simple randomized on-line algorithm for the paging\nproblem, and gives a proof that its performance guarantee (competitive ratio)\nis O(log k). In contrast, no deterministic on-line algorithm can have a\nperformance guarantee better than k.\n
Keywords
Computer ScienceEngineering
Communications of the ACMAmortized efficiency of list update and paging rules
2,109 Citations1985Daniel D. Sleator, Robert E. Tarjan
This article shows that move-to-front is within a constant factor of optimum among a wide class of list maintenance rules, and analyzes the amortized complexity of LRU, showing that its efficiency differs from that of the off-line paging rule by a factor that depends on the size of fast memory.
AlgorithmicaCompetitive snoopy caching
612 Citations1988Anna R. Karlin, Mark S. Manasse +2 more
This work presents new on-line algorithms to be used by the caches of snoopy cache multiprocessor systems to decide which blocks to retain and which to drop in order to minimize communication over the bus.
Journal of AlgorithmsCompetitive algorithms for server problems
425 Citations1990Mark S. Manasse, Lyle A. McGeoch +1 more
This paper seeks to develop on-line algorithms whose performance on any sequence of requests is as close as possible to the performance of the optimum off-line algorithm.
Competitive algorithms for on-line problems
353 Citations1988Mark S. Manasse, Lyle A. McGeoch +1 more
This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.
AlgorithmicaCompetitive randomized algorithms for nonuniform problems
261 Citations1994Anna R. Karlin, Mark S. Manasse +2 more
New randomized on-line algorithms for snoopy caching and the spin-block problem are presented and achieve competitive ratios approachinge/(e−1) ≈ 1.58 against an oblivious adversary, a surprising improvement over the best possible ratio in the deterministic case.
AlgorithmicaA strongly competitive randomized paging algorithm
241 Citations1991Lyle A. McGeoch, Daniel D. Sleator
The partitioning algorithm is developed, a randomized on-line algorithm for the paging problem, which it is proved that its expected cost on any sequence of requests is within a factor ofHk of optimum.
SIAM Journal on Discrete MathematicsNew Ressults on Server Problems
209 Citations1991Marek Chrobák, H. Karloof +2 more
A fast algorithm for oflline computing of an optimal schedule is given, and it is shown that finding an optimal offline schedule is at least as hard as the assignment problem.
An optimal online algorithm for metrical task systems
164 Citations1987Allan Borodin, Nathan Linial +1 more
A general model for the processing of sequences of tasks and a general online decision algorithm are introduced and it is shown that this algorithm is optimal among all online algorithms.
SIAM Journal on ComputingAn Optimal On-Line Algorithm for <i>K</i> Servers on Trees
159 Citations1991Marek Chrobák, Lawrence L. Larmore
The k-server problem is investigated when the metric space is a tree and an on-line k-competitive algorithm for k-servers is presented that is memoryless, in the sense that it does not use any information from the past.
Symposium on Discrete AlgorithmsCompetitive randomized algorithms for non-uniform problems
158 Citations1990Anna R. Karlin, Mark S. Manasse +2 more
Journal of Computer and System SciencesCompetitive k-server algorithms
134 Citations1994Amos Fiat, Yuval Rabani +1 more
IBM Journal of Research and DevelopmentMemory versus randomization in on-line algorithms
119 Citations1994P. Rajhavan, Marc Snir
Journal of the ACMRandom walks on weighted graphs and applications to on-line algorithms
90 Citations1993Don Coppersmith, Peter G. Doyle +2 more
This work studies the design and analysis of randomized on-line algorithms and shows that this problem is closely related to the synthesis of random walks on graphs with positive real costs on their edges.
Random walks on weighted graphs, and applications to on-line algorithms
57 Citations1990Don Coppersmith, Peter G. Doyle +2 more
A random walk with optimal stretch is obtained by computing the resistive inverse of the cost matrix (cij): a network of branch conductances (σij ≥ 0), so that, for any i, j, cij is the effective (not branch)
Symposium on Discrete AlgorithmsNew results on server problems
54 Citations1990Marek Chrobák, Howard Karloff +2 more
Competitive k-server algorithms
48 Citations2002Amos Fiat, Yuval Rabani +1 more
Deterministic competitive k-server algorithms are given for all k and all metric spaces and the competitive ratio can be proved is exponential in the number of servers, settling the k- server conjecture.
Information Processing LettersA competitive 2-server algorithm
29 Citations1991Sandy Irani, Ronitt Rubinfeld
An on-line algorithm for the 2-server problem in any metric space is given; it sends the server that minimizes the quality and is the first provable competitive rule that can be evaluated in a constant number of arithmetic operations per request with only one variable.