TY - JOUR A1 - Gottschalk, Corinna A1 - Koster, Arie M.C.A. A1 - Liers, Frauke A1 - Peis, Britta A1 - Schmand, Daniel A1 - Wierz, Andreas T1 - Robust Flows over Time: Models and Complexity Results N2 - We study dynamic network flows with uncertain input data under a robust optimization perspective. In the dynamic maximum flow problem, the goal is to maximize the flow reaching the sink within a given time horizon T, while flow requires a certain travel time to traverse an arc. In our setting, we account for uncertain travel times of flow. We investigate maximum flows over time under the assumption that at most Γ travel times may be prolonged simultaneously due to delay. We develop and study a mathematical model for this problem. As the dynamic robust flow problem generalizes the static version, it is NP-hard to compute an optimal flow. However, our dynamic version is considerably more complex than the static version. We show that it is NP-hard to verify feasibility of a given candidate solution. Furthermore, we investigate temporally repeated flows and show that in contrast to the non-robust case (i.e., without uncertainties) they no longer provide optimal solutions for the robust problem, but rather yield a worst case optimality gap of at least T. We finally show that for infinite delays, the optimality gap is at most O(k log T), where k is a newly introduced instance characteristic. The results obtained in this paper yield a first step towards understanding robust dynamic flow problems with uncertain travel times. KW - Dynamic Network Flows KW - Uncertain Travel Times KW - Dynamic Robust Flow Y1 - 2017 U6 - https://doi.org/10.1007/s10107-017-1170-3 ER -