The relative worst order ratio for online algorithms
From MaRDI portal
Publication:2944559
DOI10.1145/1240233.1240245zbMath1321.68512OpenAlexW2070091108MaRDI QIDQ2944559
Lene Monrad Favrholdt, Joan. Boyar
Publication date: 2 September 2015
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1240233.1240245
Analysis of algorithms and problem complexity (68Q25) Online algorithms; streaming algorithms (68W27)
Related Items (24)
Online-bounded analysis ⋮ On the relative dominance of paging algorithms ⋮ Online bin covering: expectations vs. guarantees ⋮ Online Dual Edge Coloring of Paths and Trees ⋮ Evaluating the quality of online optimization algorithms by discrete event simulation ⋮ Adding isolated vertices makes some greedy online algorithms optimal ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ An On-line Competitive Algorithm for Coloring $$P_8$$-free Bipartite Graphs ⋮ On the advice complexity of online bipartite matching and online stable marriage ⋮ Relative Worst-Order Analysis: A Survey ⋮ Online edge coloring of paths and trees with a fixed number of colors ⋮ On the absolute approximation ratio for first fit and related results ⋮ A comparison of performance measures via online search ⋮ Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ A comparison of performance measures for online algorithms ⋮ An on-line competitive algorithm for coloring bipartite graphs without long induced paths ⋮ Comparing first-fit and next-fit for online edge coloring ⋮ Online Bounded Analysis ⋮ Relative interval analysis of paging algorithms on access graphs ⋮ A Survey of Algorithms and Models for List Update ⋮ Comparing the costs of any fit algorithms for bin packing ⋮ Online Bin Covering: Expectations vs. Guarantees ⋮ Parameterized analysis of paging and list update algorithms
This page was built for publication: The relative worst order ratio for online algorithms
