A comparison of performance measures for online algorithms

DOI10.1007/s00453-014-9884-6zbMath1319.68256arXiv0806.0983MaRDI 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 measures; online algorithms; \(K\)-server problem

Mathematics Subject Classification ID

68W27: Online algorithms; streaming algorithms

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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