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 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. Moreover, the time for sending flow through an edge is not zero and 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 suitable for students in the Diploma programs who have already attended some courses in discrete mathematics. It is also 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) |
| First Class: | April 14, 2009 |
Dr. U. Brenner