An FPTAS for Flows over Time with Aggregate Arc Capacities

摘要

We study flows over time in networks with transit times on the arcs. Transit times describe how long it takes to traverse an arc. A flow over time specifies for each arc a time-dependent flow rate that must always be bounded by the arc's capacity. Only recently, Melkonian introduced an alternative model where so-called bridge capacities bound the total amount of flow traveling along an arc, at any point of time. The contribution of this paper is twofold. Firstly, we introduce a common generalization of both the classical flow over time model and Melko-nian's model. Secondly, we present a non-trivial extension of an FPTAS by Fleischer and Skutella to our new flow model. Prior to this, no approximation algorithm was known for Melkonian's model.