The complexity of paging against a probabilistic adversary

DOI10.1007/978-3-662-49192-8_22MaRDI QIDQ2794365zbMATH OpenOpenAlexFDO

Authors Stefan Dobrev, Juraj Hromkovič, Dennis Komm, Richard Královič, Rastislav Královič, Tobias Mömke

Publication date 10 March 2016

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

Full work available at URL https://doi.org/10.1007/978-3-662-49192-8_22

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)

Recommendations

• A strongly competitive randomized paging algorithm
• Competitive analysis of randomized paging algorithms
• Competitive analysis of randomized paging algorithms
• OnlineMin: a fast strongly competitive randomized paging algorithm
• On-Line Paging Against Adversarially Biased Random Inputs

Cited in

(4)

• Entropy-based bounds for online algorithms
• Online graph coloring against a randomized adversary
• Online Matching in Regular Bipartite Graphs with Randomized Adversary
• A universal online caching algorithm based on pattern matching

This page was built for publication: The complexity of paging against a probabilistic adversary

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2794365)