NDMI018 - Aproximační a online algoritmy

LS 2010 - Jiří Sgall

Úkoly a cvičení

Probraná témata

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

Literatura

Pro aproximační algoritmy 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

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.