NDMI018 - Aproximační a online algoritmy

LS 2016 - Jiří Sgall

UMLUVENO: úterý 12:20 v posluchárně S8

Cvičení tentokrát vede Dušan Knop.

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

1. (1. 3.)

úvod, definice aproximačního poměru
rozvrhování, hladový algoritmus (LIST) [WS 2.3]
definice: pseudopolynomiální alg., silně NP-těžké úlohy [WS 3, V8]
definice: PTAS a FPTAS [WS 3, V8]
(F)PTAS pro rozvrhování na identických počítačích [WS 3.2, V10]

2. (8. 3.) plán

(F)PTAS pro rozvrhování na identických počítačích - dokončení
bin packing, FIRST FIT [WS 3.3, V9]

3. (15. 3.) a další plán

asymptotické PTAS pro bin packing [WS 3.3, V9]
PTAS pro TSP v rovině [WS 10.1, V 11]

4. (22. 3.)

PTAS pro TSP v rovině (dokončení)
2-aproximační algoritmus for scheduling on unrelated machines [V 17, WS 11.1]

5. (29. 3.)

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

6. (5. 4.)

semidefinitní a vektorové programování [WS 6.1, V 26.1-26.3]
MAXCUT pomocí semidefinitního programování [WS 6.2, V 26.4-26.5]
chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami [WS 6.5 bez důkazu, WS 13.2]

7. (12. 4.)

chromatické číslo, algoritmus pro obarvení 3-chromatických grafů O(n^1/4) barvami
prohledávání přímky deterministicky

8. (19. 4.)

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

přesný algoritmus se známým optimem [ES2]
horní odhad pro deterministické algoritmy (dvojnásobící algoritmy) [ES2]
horní odhad pro pravděpodobnostní algoritmy (dvojnásobící algoritmy) [ES2]
dolní odhad pro online rozvrhování na počítačích různých rychlostí (preemptivní i nepreemptivní) [ES1]

9. (26. 4.)

online nepreemptivní rozvrhování na počítačích různých rychlostí - přehled výsledků [S]
problém paging, deterministické horní odhady [BE 3]

10. (3. 5.)

pravděpodobnostní algoritmy pro paging, 2H_k horní odhad [BE 4]
pravděpodobnostní algoritmy pro paging, H_k dolní odhad [BE 4]
k-server problém, definice, přehled výsledků [BE 10.1-10.4, BE 10.7]

11. (10. 5.) a další plán

k-server problém, dolní odhad k v libovolném metrickém prostroru [BE 10.1-10.3]
k-server problém na přímce [BE 10.4]
k-server problém na stromech [BE 10.4]
work function algoritmus pro k-server [BE 10.7 bez důkazu]

12. (17. 5.)

online párování - pravděpodobnostní algoritmus [BM]
dokazování neaproximace L-redukcemi [WS 16.2]

13. (24. 5.)

PCP věta a její použití, gap preserving redukce, příklady [WS 16.3]
unique games conjecture [WS 13.3, WS 16.5 bez důkazů]

na cvičeních

ski rental - deterministický a pravděpodobnostní algoritmus

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

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

[WS] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, Cambridge university press, 2011.
[V] V. V. Vazirani: Approximation Algorithms, Springer, 2001.
[BE] A. Borodin, R. El-Yaniv: Online computation and competitive analysis. Cambridge university press, 1998.
[FG] A. Fiat, G. Woeginger: Online Algorithms - The State of the Art, LNCS 1442, Springer, 1998.

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.

Články

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

[S] 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.

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

[ES2] 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.