Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, February 17, 2004, 12:15 pm
Duration: This information is not available in the database
Location: This information is not available in the database
Speaker: Alexander Hall
Flow variation over time is an important feature in network flow
problems arising in various applications such as road or air traffic
control, production systems, communication networks (e.g., the
Internet), and financial flows. The common characteristic are
networks with capacities and transit times on the edges which specify
the amount of time it takes for flow to travel through a particular
edge. Moreover, in contrast to static flow problems, flow values on
edges may change with time in these networks.
I will give a short introduction to the flows over time problem and mention new complexity and inapproximability results for the case where the transit times are assumed to be constant.
In many real-world applications transit times are not constant but depend on the current flow situation in the network. For the model where the transit time of an edge is given as a nondecreasing function of the rate of inflow into the edge I will present the ideas underlying an FPTAS for the `quickest multicommodity flow problem with bounded cost'. It can be shown that this problem is NP-hard even in the single commodity case.
This is joint work with Steffen Hippler, Katharina Langkau, and Martin Skutella.
Automatic MiSe System Software Version 1.4803M | admin login