Main
Home
/
Tags
/
Yao-principle
Yao-principle
1 page tagged.
Computer science / Coursework / Randomized algorithms
Lecture 4.1: Design Methods I
Catalogue of randomized-design methods; the first beats the worst case by randomizing the strategy. Paging k-hard; two-job scheduling 9/8-hard deterministically but →1 randomized; Yao's principle.