A classical application of minimum-cost flow problems is the transportation of goods in a street or railroad network. Here, goods have to be shipped from some sources (e.g. factories, mines, or farms) to some sinks (e.g. customers) via connections with limited capacity. Each connection has a certain cost per unit, and the goal is e.g. to minimise the total transportation cost. However, modelling such problems as standard minimum-cost flow problems is misleading because the flow on the edges may vary over time in this application. Hence, the total amount of flow that can be shipped through an edge may exceed significantly the amount of flow that can be shipped at the same time, which cannot be modelled by simply assigning capacities to the edges. Moreover, the time for sending flow through an edge may even depend on the utilisation of the edge.
In this lecture, we will see how time-dependency of flows can be modelled, and we will examine algorithmical approaches to such dynamic flow problems.
This lecture course is part of the Master's Programs in Mathematics and is as well suitable for students in the Diploma programs who have already attended some courses in discrete mathematics. 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