Aproximační a online algoritmy

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ů.