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í

Výsledky

Probraná témata

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

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 (letos jsme neprobírali), 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. 2010

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

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.