Abstract flows over time: A first step towards solving dynamic packing problems

作者：Kappmeier Jan Philipp W; Matuschke Jannik^*; Peis Britta

来源：Theoretical Computer Science, 2014, 544: 74-83.

DOI：10.1016/j.tcs.2014.04.012

• Abstract flows
• Combinatorial optimization
• Flows over time
• Dynamic packing problems

Flows over time generalize classic network flows by introducing a notion of time. Each arc is equipped with a transit time that specifies how long flow takes to traverse it, while flow rates may vary over time within the given edge capacities. This article extends the concept of an optimization problem over time to the more general setting of abstract flows. In this model, the underlying network is replaced by an abstract system of linearly ordered sets, called %26quot;paths%26quot; satisfying a simple switching property: Whenever two paths I) and Q intersect, there must be another path that is contained in the beginning of P and the end of Q. %26lt;br%26gt;We show that a maximum abstract flow over time can be obtained by solving a weighted abstract flow problem and constructing a temporally repeated flow from its solution. In the course of the proof, we also show that the relatively modest switching property of abstract networks already captures many essential properties of classic networks.

• 出版日期2014-8-7