NDMI018 - Aproximační a online algoritmy

LS 2012 - Jiří Sgall

UMLUVENO: koná se v pondělí od 9:00 v S8, cvičení následují nepravidelně od 10:40 také v S8.

Úkoly a cvičení

Cvičení se budou konat 26. 3., 16. 4., 30. 4. a 14. 5.

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

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

1. (27. 2.)

úvod, definice apx. poměru
VC 2-apx, i vážené
TSP, 1.5 apx
rozvrhování, lokální prohledávání, hladový algoritmus (LIST)

2. (5. 3.)

Nezávislá/klika - porovnání s VC
zmínění obtížnosti aproximace, unique games conjecture
hladové alg. pro rozvrhování (LIST, LPT)
definice: pseudopolynomiální alg., silně NP-těžké úlohy
definice: PTAS a FPTAS

3. (12. 3.)

bin packing, FIRST FIT
asymptotické PTAS pro bin packing
PTAS pro TSP v rovině bez důkazu
úvod do LP, algoritmy pro množinové pokrytí

4. (19. 3.)

úvod do LP
množinové pokrytí: primal-dual a analýza hladového algoritmu pomocí duálu
obtížnost aproximace, zmíněná unique games conjecture a důsledky pro množinové pokrytí a splnitelnost
algoritmy pro MAX-SAT: náhodný a zaokrouhlování LP

5. (26. 3.)

algoritmy pro MAX-SAT: náhodný výběr ze 2 algoritmů, zaokrouhlování s nelineární funkcí
derandomizace metodou podmíněných pravděpodobností
semidefinitní a vektorové programování
MAXCUT pomocí semidefinitního programování

6. (2. 4.)

MAXCUT pomocí SDP, dokončení
chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami

7. (16. 4.)

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

8. (23. 4.)

prohledávání přímky deterministicky
problém paging, deterministické horní odhady
pravděpodobnostní algoritmy pro paging, 2H_k horní odhad

9. (30. 4.)

pravděpodobnostní algoritmy pro paging, H_k dolní odhad
k-server problém, definice, přehled výsledků
k-server problém, dolní odhad k v libovolném metrickém prostroru
k-server problém na přímce

10. (7. 5.)

k-server problém na stromech
work function algoritmus pro k-server

11. (14. 5.)
12. (21. 5.)

v domácím úkolu: LPT pro rozvrhování, ATSP, ski renal (půjčování auta)
odloženo

LIST pro rozvrhování se závislostmi

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

Lecture notes (online)

David Williamson - kurs aproximačních algoritmů: http://kam.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

A. Blum, P. Raghavan, and B. Schieber. Navigating in Unfamiliar Geometric Terrain. SIAM J. Comp 26(1):110-137, February 1997. An earlier version appears in Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, pages 494-504, May 1991.

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.