Algorytmy online 2022/23

(12.10.2022) 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 12th World Computer Congress, 1992
R. Baeza-Yates, J. Culberson, G. Rawlins: Searching in the plane. Information and Computation, 1993

(26.10.2022) Zasada zaznaczania: problem pamięci podręcznej, algorytmy zaznaczające, LRU, dolne ograniczenie, randomizowane algorytmy zaznaczające.

- 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.

(9.11.2022) Zasada zaznaczania: problem metrycznych systemów zadań. Funkcje potencjału: analiza zamortyzowana w algorytmach online, problem reorganizacji listy, algorytm MTF, dolne ograniczenie przez argument o średniej.

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.
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.

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

Dolne ograniczenia dla algorytmów randomizowanych: zasady 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

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. J. ACM 1997

Schemat prymalno-dualny: programowanie liniowe, problem pokrywania zbiorami.
- - - N. Buchbinder, J. Naor: Online primal–dual algorithms for covering and packing problems. ESA 2005
    - N. Buchbinder, J. Naor: The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in TCS, 2009

Routing. Dolne ograniczenie dla małych przepustowości. Algorytm prymalno-dualny (multiplikatywne wagi) dla dużych przepustowości.
- - - B. Awerbuch, Y. Azar, S. Plotkin: Troughput competitive on-line routing, FOCS 1993
    - N. Buchbinder, J. Naor: The Design of Competitive Online Algorithms via a Primal-Dual Approach. Foundations and Trends in TCS, 2009

Routing cd. Technika classify-and-randomly-select.
Problem k serwisantów (k-server): dolne ograniczenie, algorytm Double Coverage dla prostej.

E. Koutsoupias: The k-server problem. Computer Science Review, 2009
M. Chrobak, L. Larmore: An optimal algorithm for the server problem on trees. SIAM J. Computing, 1991

Migracja pliku: algorytm randomizowany Flip, algorytm deterministyczny Move-To-Min, informacja o factor-revealing LP.
- - - J. Westbrook: Randomized Algorithms for Multiprocessor Page Migration. SIAM J. Computing, 1994
    - Baruch Awerbuch, Yair Bartal, Amos Fiat: Competitive distributed file allocation. Inf. Comput., 2003.
    - M. Bieńkowski, J Byrka, M. Mucha: Dynamic beats fixed: On phase-based algorithms for file migration. Trans. Algorithms 2019

Funkcje pracy (work functions): optymalny algorytm dla metrycznych systemów zadań.
- - - A. Borodin, N. Linial, M. Saks: An optimal on-line algorithm for metrical task system. J. ACM, 1992
    - M. Chrobak, L. Larmore, N. Reingold, J. Westbrook: Page Migration Algorithms Using Work Functions. J. Algorithms, 1997

Przybliżanie grafów za pomocą drzew.
- Prezentacja z wykładu
- J. Fakcharoenphol, S. Rao, K. Talwar: A tight bound on approximating arbitrary metrics by tree metrics. JCSS 2004

Zaokrąglanie Przybliżanie grafów za pomocą drzew.
- N. Alon, B. Awerbuch, Y. Azar, N. Buchbinder, J. Naor: The online set cover problem. STOC 2003

Egzamin będzie ustny.
Będzie można mieć własne notatki.
Egzamin sprawdza zrozumienie i umiejętność odtworzenia twierdzeń i dowodów z wykładu, lecz mogą też pojawić się zadania podobne do przerabianych na ćwiczeniach.
Ocena z egzaminu jest wpisywana w obie rubryki: ćwiczenia i egzamin w USOSie.

Można opuścić bez usprawiedliwienia do dwóch ćwiczeń.
Zadania należy oddawać pisemnie do 10:15 w środy (przed wykładem) na kartce
Będzie co najmniej 12 list ćwiczeń, każda po 10 pkt. Każde 30 punktów podnosi ocenę z egzaminu (w przypadku jego zdania) o 0,5 stopnia.
Zadania można robić samodzielnie lub w grupach maksymalnie 3-osobowych. Każda osoba z grupy powinna umieć zaprezentować wszystkie oddawane zadania.