5 listopada
Przegląd sekcji
-
Wykład 4: Funkcje potencjału dla algorytmów randomizowanych: algorytm BIT dla problemu reorganizacji listy, algorytm RAND dla problemu pamięci podręcznej, informacja o adwersarzach adaptujących się.
- N. Reingold, J. Westbrook, D. Sleator: Randomized Competitive Algorithms for the List Update Problem. Algorithmica, 1992
- P. Raghavan, M. Snir: Memory versus randomization in on-line algorithms. IBM Journal of Research and Development, 1994
- S. Ben-David, A. Borodin, R. Karp, G. Tardos, A. Wigderson: On the power of randomization in on-line algorithms, Algorithmica, 1994