On randomization in on-line computation.

DOI10.1006/INCO.1998.2775MaRDI QIDQ1854274zbMATH OpenOpenAlexFDO

Authors Allan Borodin, Ran El-Yaniv

Publication date 14 January 2003

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://semanticscholar.org/paper/84622da1f3cd2c5323f695ec084e04120c2031e3

zbMATH Keywords

randomized on-line algorithmsYao principle

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Theory of operating systems (68N25)

Recommendations

• A strongly competitive randomized paging algorithm
• Competitive analysis of randomized paging algorithms
• On the power of randomization in on-line algorithms
• Competitive analysis of randomized paging algorithms
• Competitive randomized algorithms for nonuniform problems

Cites work

• scientific article; zbMATH DE number 3128727 (Why is no real title available?)
• scientific article; zbMATH DE number 49749 (Why is no real title available?)
• scientific article; zbMATH DE number 1226083 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 3277161 (Why is no real title available?)
• scientific article; zbMATH DE number 3302001 (Why is no real title available?)
• An optimal on-line algorithm for metrical task system
• Competitive paging algorithms
• New Ressults on Server Problems
• On the power of randomization in on-line algorithms

Cited in

(10)

• Online k-server routing problems
• Randomized algorithms for on-line scheduling problems: How low can't you go?
• On the power of randomization in on-line algorithms
• Min-cost bipartite perfect matching with delays
• Metrical service systems with multiple servers
• On the online min-wait relocation problem
• A guessing game and randomized online algorithms
• Randomized algorithms for online bounded bidding
• Randomized distributed online algorithms against adaptive offline adversaries
• Online paging with heterogeneous cache slots

This page was built for publication: On randomization in on-line computation.

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