Flows, Paths and Cuts - NDMI067
Title: Toky, cesty a řezy Department of Applied Mathematics (32-KAM) Faculty of Mathematics and Physics from 2021 to 2023 winter 3 winter s.:2/0, Ex [HT] unlimited unlimited no no taught Czech, English full-time full-time
Guarantor: doc. Mgr. Petr Kolman, Ph.D. doc. Mgr. Petr Kolman, Ph.D. Informatika Mgr. - Diskrétní modely a algoritmy Informatics > Discrete Mathematics
 Annotation - ---CzechEnglish
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.
Last update: T_KAM (21.04.2016)
 Course completion requirements - ---CzechEnglish

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

Last update: Kolman Petr, doc. Mgr., Ph.D. (12.10.2017)
 Literature - ---CzechEnglish

[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

Last update: Kolman Petr, doc. Mgr., Ph.D. (12.10.2017)
 Syllabus - ---CzechEnglish

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.

Last update: G_I (08.06.2007)