|
|
|
||
Last update: T_KAM (21.04.2016)
|
|
||
Last update: doc. Mgr. Petr Kolman, Ph.D. (12.10.2017)
The exam is oral. The requirements correspond to the syllabus as covered by the lectures. |
|
||
Last update: 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 |
|
||
Last update: 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. |