DMI018 - Aproximační a online algoritmy

DMI018 - Aproximační a online algoritmy
ZS 2001

Zajišťuje: KAM
Vyučující: Jiří Sgall
Rozsah v ZS: 2/0 Zk
Rozsah v LS: ---
Třída: I

Anotace

Pro mnohé optimalizační problémy je obtížné navrhonout 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í. Typický příklad je rozvrhování úloh na několika počítačích. Je poměrně jednoduché nalézt algoritmus, který vždy vrátí rozvrh nejvýše dvakrát delší než optimální. Použitím složitějších metod je však možné efektivně nalézt i např. rozvrh jen o jedno procento delší než optimální. Tzv. online algoritmy se studují v situaci, kdy není předem znám celý vstup. Např. při rozvrhování je možné, že úlohy dostáváme postupně, ale přidělit je jednotlivým počítačům musíme ihned.

Přednáška se zaměří na teoretické studium aproximačních a online algoritmů pro různé problémy. Přednáška je určena především studentům vyšších ročníků, případně i doktorandům. Předpokládá se znalost základních pojmů z a teorie algoritmů (např. DMI026). Přednášející v tomto oboru pracuje a publikuje.

Osnova

Základní pojmy, aproximační a kompetitivní poměr, polynomiální aproximační schémata.
Různé modely rozvrhování a "bin packing", hladový algoritmus, další aproximační a online algoritmy.
Kombinatorické problémy: nezávislé množiny, "set cover", minimální řez atd.
Použití metod lineárního a semidefinitního programování v aproximačních algoritmech.
Metody pro dokazování obtížnosti i přibližného řešení kombinatorických problémů, tzv. PCP věta.
Online algoritmy pro paging (caching). Tzv. k-server problém.
Podle času a zájmu některé další oblasti: pohyb v neznámém prostředí, směrování v sítích nebo finanční problémy.

Základní lit.

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.

Doplň.popis

Přednáška se nekoná každý rok, předpokládám její opakování za 2-3 roky. Úmluva bude v prvním týdnu semestru na KAM, v rámci hromadné úmluvy na výběrové přednášky KAM. Kontakt: sgall@math.cas.cz, http://www.math.cas.cz/~sgall/, tel. 22090780.

28. 3. 2001