PCP věta a její použití, gap preserving redukce,
příklady [WS 16.3]
11. (22. 5.)
dokazování neaproximace L-redukcemi [WS 16.2]
unique games conjecture [WS 13.3, WS 16.5 bez důkazů]
Další plán podle předchozího běhu
zatím vynechaná témata
PTAS pro TSP v rovině [WS 10.1, V 11]
2-aproximační algoritmus for scheduling on unrelated
machines [V 17, WS 11.1]
na cvičeních
ski rental - deterministický a pravděpodobnostní algoritmus
prohledávání přímky deterministicky
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. 2016
[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.
[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.