Sylabus
Probírané techniky:
- Základní pojmy, aproximační a kompetitivní poměr
- Polynomiální aproximační schémata, jejich vztah k silné NP-úplnosti
- Pokročilé použití metod lineárního programování v aproximačních algoritmech: zaokrouhlování, primárně-duální algoritmy
- Použití metod semidefinitního programování v aproximačních algoritmech
- Použití potenciálu pro online algoritmy
- Metody pro dokazování obtížnosti i přibližného řešení kombinatorických problémů: L-redukce, APX-úplnost, PCP věta
Probírané problémy a algoritmy:
- Různé modely rozvrhování a "bin packing", hladový algoritmus, další aproximační a online algoritmy
- Kombinatorické problémy: Steinerův strom, maximální řez, barvení grafů
- Online algoritmy pro paging (caching) a k-server problém
- Online algoritmy pro pohyb v neznámém prostředí
Anotace
Pro mnohé optimalizační problémy je obtížné navrhnout algoritmy, které je vyřeší optimálně a zároveň rychle
(např. pro NP-úplné problémy). V takovém případě studujeme tzv. aproximační algoritmy, které pracují rychle, a najdou řešení více či méně blízké optimálnímu řešení. Tzv. online algoritmy se studují v situaci, kde není předem znám celý vstup. Přednáška se zaměří na teoretické studium aproximačních a online algoritmů pro různé problémy. Předpokládá se znalost na úrovni Bc. předmětu NDMI084 Úvod do aproximačních a pravděpodobnostních algoritmů.