Relative Worst-Order Analysis: A Survey
From MaRDI portal
Publication:6163627
DOI10.1007/978-3-319-98355-4_13zbMath1514.68319arXiv1802.07080OpenAlexW4214627562MaRDI QIDQ6163627
Joan. Boyar, Lene Monrad Favrholdt, Kim S. Larsen
Publication date: 30 June 2023
Published in: Adventures Between Lower Bounds and Higher Altitudes (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.07080
Related Items (2)
Online minimum spanning trees with weight predictions ⋮ Stochastic dominance and the bijective ratio of online algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Online bin covering: expectations vs. guarantees
- A comparison of performance measures for online algorithms
- Online algorithms with advice: the tape model
- A theoretical comparison of LRU and LRU-K
- A combined BIT and TIMESTAMP algorithm for the list update problem
- A lower bound for randomized list update algorithms
- List's worst-average-case or WAC ratio
- On the relative dominance of paging algorithms
- The relative worst-order ratio applied to paging
- Random-order bin packing
- Bincoloring
- Scheduling jobs on grid processors
- Tight results for next fit and worst fit with resource augmentation
- Competitive snoopy caching
- Two results on the list update problem
- LRU is better than FIFO
- A new measure for the study of on-line algorithms
- Online-bounded analysis
- Fast algorithms for bin packing
- Competitive paging with locality of reference
- List factoring and relative worst order analysis
- The seat reservation problem
- Separating online scheduling algorithms with the relative worst order ratio
- Comparing online algorithms for bin packing problems
- A comparison of performance measures via online search
- Relative interval analysis of paging algorithms on access graphs
- The Accommodating Function: A Generalization of the Competitive Ratio
- Probabilistic Analysis of the Dual Next-Fit Algorithm for Bin Covering
- Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
- The relative worst order ratio for online algorithms
- The Frequent Items Problem in Online Streaming Under Various Performance Measures
- New Ressults on Server Problems
- Online Appointment Scheduling in the Random Order Model
- Smoothed analysis of algorithms
- Information Complexity of Online Problems
- A Knapsack Secretary Problem with Applications
- Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms
- Improved Randomized On-Line Algorithms for the List Update Problem
- Speed is as powerful as clairvoyance
- Beyond Competitive Analysis
- The relative worst order ratio applied to seat reservation
- Measuring the problem-relevant information in input
- On Serial Files with Relocatable Records
- The working set model for program behavior
- Bounds on Multiprocessing Timing Anomalies
- On paging with locality of reference
This page was built for publication: Relative Worst-Order Analysis: A Survey
