Flows Over Time - Complexity, Approximation, and Modeling
The intention of the talk 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 modeled 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. We discuss recent approximation results for flows over time with multiple commodities, costs, or flow-dependent transit times.