Algorytmy online 2025/26
Przegląd sekcji
-
Wykład 1. Wstęp do algorytmów online: konkurencyjność, przykładowe problemy i algorytmy online: wypożyczanie nart, spin-block, eksploracja prostej, pakowanie pojemników.
- A. Borodin, R. El-Yaniv: Online Computation and Competitive Analysis. Cambridge University Press, 1998
- R. Karp: On-line algorithms versus off-line algorithms: How much is it worth to know the future? IFIP World Computer Congress, 1992
- A. Karlin, M. Manasse, L. McGeoch, S. Owicki: Competitive Randomized Algorithms for Non-Uniform Problems, Algorithmica, 1994
- R. Baeza-Yates, J. Culberson, G. Rawlins: Searching in the plane. Information and Computation, 1993
Brak ćwiczeń w tym dniu.
-
Wykład 2. Zasada zaznaczania: problem pamięci podręcznej, algorytmy zaznaczające, LRU, algorytm Random Mark.
- D. Sleator, R. Tarjan: Amortized efficiency of list update and paging rules. Communications of the ACM, 1985.
- A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, N. Young: Competitive paging algorithms. Journal of Algorithms, 1991.
-
Zajęcia odwołane.
-
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
-
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
-
Wykład 5. Dolne ograniczenia dla algorytmów randomizowanych: zasada minimaksowa Yao, dolne ograniczenie dla problemu pamięci podręcznej.
- A. Fiat, R. Karp, M. Luby, L. McGeoch, D. Sleator, N. Young: Competitive paging algorithms. Journal of Algorithms, 1991
- A. Yao: Probabilistic computations: Towards a unified measure of complexity. FOCS, 1977
-
Wykład 6. Metoda podwajania: problem online bidding, szeregowanie na identycznych i powiązanych maszynach.
- M. Chrobak, C. Kenyon-Mathieu: Competitiveness via doubling. SIGACT News, 2006
- M. Chrobak, C. Kenyon, John Noga, Neal E. Young: Incremental Medians via Online Bidding. Algorithmica, 2008
- J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, O. Waarts: On-Line Routing of Virtual Circuits with Applications to Load Balancing and Machine Scheduling. Journal of ACM. 1997
-
Brak zajęć (poniedziałek w środę).