Sumários
Lecture 12
25 maio 2012, 10:00 • Alexandre Francisco
Conclusion of exercises from previous lecture. An exercise on developing online MST algorithm.
Online algorithms
21 maio 2012, 08:30 • Alexandre Francisco
Randomized online paging algorithms. Adversary models: oblivious adversary; adaptive online adversary; adaptive offline adversary; competitiveness coefficients and properties. Paging against an oblivious adversary: lower bound and the Marker algorithm.
Lecture 11
18 maio 2012, 10:00 • Alexandre Francisco
Problems 10.17 and 10.18 and exercise 6.1 from the book "Randomized Algorithms".
Online algorithms
18 maio 2012, 08:30 • Alexandre Francisco
Introduction, motivation and basic concepts. Online paging problem: definition; offline optimal algorithms; deterministic online algorithms. Competitiveness coefficient. A lower bound on the competitiveness coefficient for deterministic online paging algorithms.