A comparison of performance measures for online algorithms

DOI10.1007/s00453-014-9884-6zbMath1319.68256arXiv0806.0983OpenAlexW2017441966MaRDI QIDQ494791

Kim S. Larsen, Sandy Irani, Joan. Boyar

Publication date: 2 September 2015

Published in: Algorithmica, Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0806.0983

zbMATH Keywords

performance measuresonline algorithms\(K\)-server problem

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27)

Related Items (20)

Online bin covering: expectations vs. guarantees ⋮ Two-way and one-way quantum and classical automata with advice for online minimization problems ⋮ On the online min-wait relocation problem ⋮ Best-of-both-worlds analysis of online search ⋮ Price discrimination with robust beliefs ⋮ Classical and Quantum Computations with Restricted Memory ⋮ Relative Worst-Order Analysis: A Survey ⋮ Online minimum spanning trees with weight predictions ⋮ List factoring and relative worst order analysis ⋮ On the absolute approximation ratio for first fit and related results ⋮ A comparison of performance measures via online search ⋮ On the separation and equivalence of paging strategies and other online algorithms ⋮ Quantum online algorithms with respect to space and advice complexity ⋮ A comparison of performance measures for online algorithms ⋮ Quantum online streaming algorithms with logarithmic memory ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Relative interval analysis of paging algorithms on access graphs ⋮ Stochastic dominance and the bijective ratio of online algorithms ⋮ Online Bin Covering: Expectations vs. Guarantees

Cites Work

• A comparison of performance measures for online algorithms
• On the relative dominance of paging algorithms
• The relative worst-order ratio applied to paging
• Random-order bin packing
• Competitive snoopy caching
• A new measure for the study of on-line algorithms
• The relative worst order ratio for online algorithms
• New Ressults on Server Problems
• Competitive algorithms for server problems
• Randomized Competitive Analysis for Two-Server Problems
• Longest run of consecutive observations having a specified attribute
• Bounds for Certain Multiprocessing Anomalies
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A comparison of performance measures for online algorithms