Syllabus
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.
Annotation
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.