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.