Flows Over Time

Thursday, September 12, 2002 - 9:30am - 10:15am
Keller 3-180
Martin Skutella (Massachusetts Institute of Technology)
The intention of the tutorial is to give an introduction into the area of flows over time or dynamic flows. Flows over time have been introduced about forty years ago by Ford and Fulkerson and have many real-world applications such as, for example, traffic control, evacuation plans, production systems, communication networks, and financial flows. Flows over time are modelled in networks with capacities and transit times on the arcs. The transit time of an arc specifies the amount of time it takes for flow to travel from the tail to the head of that arc. In contrast to the classical case of static flows, a flow over time specifies a flow rate entering an arc for each point in time and the capacity of an arc limits the rate of flow into the arc at each point in time. The topics covered range from the classical results of Ford and Fulkerson on maximal s-t-flows over time to very recent approximation results for flows over time with multiple commodities and costs.