Max-flow and minimum-cost flow problems are classical optimization problems. The first applications that motivated the study of flow problems came from logistics. In such applications, goods have to be shipped from some sources (e.g. factories, mines, or farms) to sinks (e.g. customers) via connections with limited capacity. Each connection may have a certain cost per unit, and the goal is e.g. to minimize the total transportation cost. However, modeling logistic problems by standard minimum-cost flows is misleading. In standard flow problems one assumes that the whole flow runs on all edges in the networks at the same time which is not the case e.g. in street networks. More realistic models lead to dynamic (or time-depended) flows.
In this lecture, we will see how time-dependency of flows can be modeled, and we will examine algorithms to compute dynamic flows. Typically, dynamic flow problems are more difficult to solve than their static counterparts, and in several cases we will only show hardness results.
This lecture is part of the Master's Programs in Mathematics and Computer Science. Participants should be familiar with basic graph theory and the most important minimum-cost flow algorithms.
| Class Hours: | Tuesdays 10 am - 12 pm (10:15-11:45) |
| Room: | Gerhard-Konow-Hörsaal (in the Arithmeum building, Lennéstr. 2) |
Dr. U. Brenner