Toky, cesty a řezy - NDMI067

• Anglický název: Flows, Paths and Cuts
• Zajišťuje: Katedra aplikované matematiky (32-KAM)
• Fakulta: Matematicko-fyzikální fakulta
• Platnost: od 2021
• Semestr: zimní
• E-Kredity: 3
• Rozsah, examinace: zimní s.:2/0, Zk [HT]
• Počet míst: neomezen
• Minimální obsazenost: neomezen
• 4EU+: ne
• Virtuální mobilita / počet míst pro virtuální mobilitu: ne
• Stav předmětu: vyučován
• Jazyk výuky: čeština, angličtina
• Způsob výuky: prezenční
• Způsob výuky: prezenční
• Garant: doc. Mgr. Petr Kolman, Ph.D.
• Třída: Informatika Mgr. - Diskrétní modely a algoritmy
• Kategorizace předmětu: Informatika > Diskrétní matematika

Anotace

čeština

Poslední úprava: T_KAM (21.04.2016)

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.

angličtina

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.

Podmínky zakončení předmětu

čeština

Poslední úprava: doc. Mgr. Petr Kolman, Ph.D. (12.10.2017)

Zkouška je ústní. Požadavky odpovídají sylabu v míře pokryté přednáškami.

angličtina

Poslední úprava: doc. Mgr. Petr Kolman, Ph.D. (12.10.2017)

The exam is oral. The requirements correspond to the syllabus as covered by the lectures.

Literatura

čeština

Poslední úprava: prof. Mgr. Milan Hladík, Ph.D. (25.04.2012)

[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

angličtina

Poslední úprava: doc. Mgr. Petr Kolman, Ph.D. (12.10.2017)

[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

Sylabus

čeština

Poslední úprava: G_I (08.06.2007)

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

angličtina

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.