29 października
Section outline
-
Wykład 3. Zasada zaznaczania: metryczne systemy zadań. Funkcje potencjału: analiza zamortyzowana w algorytmach online, problem reorganizacji listy, algorytm MTF, dolne ograniczenie przez argument o średniej.
- A. Borodin, N. Linial, M. Saks: An optimal on-line algorithm for metrical task system, Journal of ACM, 1992
- A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis. Cambridge University Press, 1998
- D. Sleator, R. Tarjan: Amortized efficiency of list update and paging rules. Communications of the ACM, 1985