Toky, cesty a řezy

Sylabus

Toky více komodit zobecňují přirozeným způsobem klasický tokový problém: místo jediné dvojice zdroj-spotřebič máme takových dvojic několik, ale přitom máme k dispozici stále jen jedinou síť, do které se musí všechny toky poskládat. Toky více komodit a zejména jejich duální řezové problémy hrály v posledním desetiletí významnou úlohu při návrhu aproximačních algoritmů pro celou radu rozmanitých aplikací.

Cílem přednášky je představit vybrané výsledky z této oblasti a ukázat na nich několik obecných postupů užitečných při návrhu aproximačních algoritmů.

Anotace

Toky více komodit zobecňují přirozeným způsobem klasický tokový problém: místo jediné dvojice zdroj-spotřebič máme takových dvojic několik, ale přitom máme k dispozici stále jen jedinou síť, do které se musí všechny toky poskládat. Toky více komodit a zejména jejich duální řezové problémy hrály v posledním desetiletí významnou

úlohu při návrhu aproximačních algoritmů pro celou radu rozmanitých aplikací. Cílem přednášky je představit vybrané výsledky z této oblasti a ukázat na nich několik obecných postupů užitečných při návrhu aproximačních algoritmů. Predmet se uci jednou za dva roky.