Ausiello, P. Crescenzi,G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi – Complexity and Approximation – Combinatorial optimization problems and their approximability properties. Springer Verlag, 2000
J.Hromkovič: Algorithmics for Hard Problems, Springer, 2001
Vijay V. Vazirani: Approximation Algorithms, Springer-Verlag, Berlin, 2001
odborné články
elektronické študijné texty
2-INF-221 Aproximácia optimalizačných problémov
| Odporúčaný ročník: | 2. |
| Semester: | zimný |
| Rozsah: | P4 |
| Hodnotenie: | 30/70 |
| Počet kreditov: | 6 |
| Vyučujúci: | prednáša prof. RNDr. Rastislav Královič PhD. |
| www stránka: | http://kedrigern.dcs.fmph.uniba.sk/apx/ |
Cieľ:
Skúmať hierarchiu NP-úplných problémov z pohľadu aproximovateľnosti. Priblížiť moderné techniky návrhu a analýzy aproximačných algoritmov.
Sylabus:
Predmet priamo nadväzuje na predmet 2-INF-167 (Výpočtová zložitosť a vypočítateľnosť). Detailnejšie rozpracováva oblasť aproximačných algorimov a zahŕňa techniky návrhu aproximačných algoritmov, dôkazové techniky na odhad aproximačného faktora, neaproximovateľnosť a PCP vetu, triedy aproximovateľnosti a ich úplné problémy, asymptotickú aproximovateľnosť.
Literatúra: