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