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.
Poslední úprava: T_KAM (21.04.2016)
Multicommodity flows genaralize in a natural way the classical flow problem: instead of just a single source-
destination pair, there are several such pairs but there is still just one network and all flows must fit in it.
Multicommodity flows and their dual cut problems are extremely useful in the design of approximation algorithms
for many different graph problems. The lecture will provide an overview of the most important result in this area.
The course is taught once in two years.
Poslední úprava: T_KAM (21.04.2016)
Podmínky zakončení předmětu -
Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami.
Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (12.10.2017)
The exam is oral. The requirements correspond to the syllabus as covered by the lectures.
Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (12.10.2017)
Literatura -
[1] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, http://www.designofapproxalgs.com/book.pdf (dostupne online)
[2] V. Vazirani: Approximation Algorithms
Poslední úprava: Hladík Milan, prof. Mgr., Ph.D. (25.04.2012)
[1] D. P. Williamson, D. B. Shmoys: The Design of Approximation Algorithms, http://www.designofapproxalgs.com/book.pdf (available online)
[2] V. Vazirani: Approximation Algorithms
Poslední úprava: Kolman Petr, doc. Mgr., Ph.D. (12.10.2017)
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ů.
Poslední úprava: G_I (08.06.2007)
Multicommodity flows are a natural generalization of the classical flow: instead of just a single source-sink pair, there are k such pairs. The objective is (e.g.) to maximize the sum of the flows for all k commodities subject to the capacity constraints. The multicommodity flows and their dual cut problems received a lot of attention in the last decade. The aim of the lecture is present the most important results from this area and to demonstrate on them general approaches useful for design of approximation algorithms for NP-hard problems.
