NDMI018 - Aproximační a online algoritmy

LS 2014 - Jiří Sgall

UMLUVENO: pondělí 14:00 v posluchárně S4
cvičení se budou konat nepravidelně po oznámení v pondělí po přednášce v S6, první budou 10. 3.

Úkoly a cvičení

1. série úkolů (termín 9. 3. nebo na přednášce 10. 3.)
2. série úkolů (termín 30. 3. nebo na přednášce 31. 3.)
3. série úkolů (termín 27. 4. nebo na přednášce 28. 4.)
4. série úkolů (termín 18. 5. nebo na přednášce 19. 5.)

Výsledky

Probraná látka podle přednášek

1. (24. 2.)

úvod, definice aproximačního poměru
příklady optimalizačních problémů, grafové problémy
TSP, 1.5 apxroximace (Christofides), O(log n) aproximace asymetrické verze
k-center problém, 2-aproximace

2. (3. 3.)

rozvrhování, lokální prohledávání, hladový algoritmus (LIST)
definice: pseudopolynomiální alg., silně NP-těžké úlohy
definice: PTAS a FPTAS
(F)PTAS pro rozvrhování na identických počítačích

3. (10. 3.)

bin packing, FIRST FIT
asymptotické PTAS pro bin packing
MAX-SAT - pravděpodobnostní algoritmus
derandomizace metodou podmíněných pravděpodobností

4. (17. 3.)

algoritmy pro MAX-SAT: zaokrouhlování LP a náhodný výběr ze 2 algoritmů
úvod do LP
množinové pokrytí: primal-dual a analýza hladového algoritmu pomocí duálu

5. (24. 3.)

nejkratší cesta - Dijkstra jako primárně duální algoritmus
zobecněný Steinerův strom - 2-aproximační primárně duální algoritmus
semidefinitní a vektorové programování

6. (31. 3.)

MAXCUT pomocí semidefinitního programování
chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami

7. (7. 4.)

problém paging, deterministické horní odhady
pravděpodobnostní algoritmy pro paging, 2H_k horní odhad
pravděpodobnostní algoritmy pro paging, H_k dolní odhad
k-server problém, definice, přehled výsledků

8. (14. 4.)

prohledávání přímky deterministicky
k-server problém, dolní odhad k v libovolném metrickém prostroru
k-server problém na přímce
k-server problém na stromech

9. (28. 4.)

online preemptivní rozvrhování na počítačích různých rychlostí

přesný algoritmus se známým optimem
horní odhad pro deterministické algoritmy (dvojnásobící algoritmy)
horní odhad pro pravděpodobnostní algoritmy (dvojnásobící algoritmy)

10. (5. 5.)

online preemptivní rozvrhování na počítačích různých rychlostí

dolní odhad pro online rozvrhování na počítačích různých rychlostí (preemptivní i nepreemptivní)

online párování - pravděpodobnostní algoritmus

11. (12. 5.)

work function algoritmus pro k-server
dokazování neaproximace L-redukcemi

12. (19. 5.)

PCP věta a její použití, gap preserving redukce, příklady
unique games conjecture

Literatura

Pro aproximační algoritmy je nejaktuálnější kniha Williamson-Shmoys, dále doporučuji poznámky Williamsona a knihu Vaziraniho. Pro online algoritmy pro paging a k-server problem knihu Borodin, El-Yaniv. Dále přikládám odkazy na články o rozvrhování. V mém přehledu je sepsaný důkaz 4/3-kompetitivního algoritmu pro 2 počítače, v dalších dvou pak dolní a horní odhad na preemptivní rozvrhování na počítačích různých rychlostí.
Předchozí běh kursu v r. 2012

Lecture notes (online)

David Williamson - kurs aproximačních algoritmů: http://iuuk.mff.cuni.cz/~sgall/vyuka/dw-notes2.ps
Avrim Blum - obdobný kurs: http://www-2.cs.cmu.edu/~avrim/Approx00/
Yossi Azar - obdobný kurs: http://www.cs.tau.ac.il/~azar/online03.html
Seffi Naor - přehledová přednáška o návrhu online algoritmů navržených pomocí primárně-duálních algoritmů

Knihy

D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.
V. V. Vazirani: Approximation Algorithms, Springer, 2001.
J. Hromkovic: Algorithmics for Hard Problems, Springer, 2001.
G. Ausiello et al: Complexity and Approximation, Springer, 1999.
D. S. Hochbaum (editor): Approximation algorithms for NP-hard problems, PWS publishing company, 1997.
A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.
A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.

Články

Benjamin Birnbaum and Claire Mathieu: On-line bipartite matching made simple
ACM SIGACT News, Volume 39 , Issue 1 (March 2008), pp. 80-87.

J. Sgall: On-line scheduling
In Online Algorithms: The State of the Art, eds.A. Fiat and G. J. Woeginger, Lecture Notes in Comput. Sci. 1442, pages 196-231, Springer, 1998.

L. Epstein, J. Sgall: A lower bound for on-line scheduling on uniformly related machines
Oper. Res. Lett., 26(1):17-22, 2000.

T. Ebenlendr, J. Sgall: Optimal and online preemptive scheduling on uniformly related machines
In Proc. of the 21st Ann. Symp. on Theor. Aspects of Comput. Sci. (STACS) , Lecture Notes in Comput. Sci. 2996, pages 199-210. Springer, 2004.