The relative worst-order ratio applied to paging

DOI10.1016/j.jcss.2007.03.001zbMath1115.68159OpenAlexW2033855099MaRDI QIDQ881599

Kim S. Larsen, Joan. Boyar, Lene Monrad Favrholdt

Publication date: 30 May 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.03.001

zbMATH Keywords

on-line algorithmspaginglook-aheadLRUrelative worst-order ratioRLRU

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05)

Related Items (24)

On the relative dominance of paging algorithms ⋮ Quantifying Competitiveness in Paging with Locality of Reference ⋮ Online bin covering: expectations vs. guarantees ⋮ Online Dual Edge Coloring of Paths and Trees ⋮ A theoretical comparison of LRU and LRU-K ⋮ The Frequent Items Problem in Online Streaming Under Various Performance Measures ⋮ Relative Worst-Order Analysis: A Survey ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ Comparing online algorithms for bin packing problems ⋮ A new variable-sized bin packing problem ⋮ List factoring and relative worst order analysis ⋮ A comparison of performance measures via online search ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ A comparison of performance measures for online algorithms ⋮ Comparing first-fit and next-fit for online edge coloring ⋮ Scheduling jobs on grid processors ⋮ Relative interval analysis of paging algorithms on access graphs ⋮ Quantifying competitiveness in paging with locality of reference ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Engineering Efficient Paging Algorithms ⋮ A Survey of Algorithms and Models for List Update ⋮ Unnamed Item ⋮ Online Bin Covering: Expectations vs. Guarantees ⋮ Parameterized analysis of paging and list update algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strongly competitive randomized paging algorithm
• Competitive snoopy caching
• On competitive on-line paging with lookahead
• LRU is better than FIFO
• A new measure for the study of on-line algorithms
• On the influence of lookahead in competitive paging algorithms
• A unified analysis of paging and caching
• Competitive analysis of randomized paging algorithms
• On-line file caching
• Fast algorithms for bin packing
• Competitive paging with locality of reference
• The seat reservation problem
• Separating online scheduling algorithms with the relative worst order ratio
• The Accommodating Function: A Generalization of the Competitive Ratio
• Union-copy structures and dynamic segment trees
• New Ressults on Server Problems
• Competitive paging algorithms
• Speed is as powerful as clairvoyance
• Markov Paging
• Algorithm Theory - SWAT 2004
• ON-LINE SEAT RESERVATIONS VIA OFF-LINE SEATING ARRANGEMENTS
• Algorithms – ESA 2004
• Bounds for Certain Multiprocessing Anomalies
• On paging with locality of reference

This page was built for publication: The relative worst-order ratio applied to paging