Abstract flows over time: a first step towards solving dynamic packing problems
From MaRDI portal
Publication:4909560
DOI10.1007/978-3-642-35261-4_46zbMATH Open1260.90140arXiv1211.2177OpenAlexW2741352694MaRDI QIDQ4909560FDOQ4909560
Authors: Jan-Philipp W. Kappmeier, Jannik Matuschke, Britta Peis 
Publication date: 21 March 2013
Published in: Algorithms and Computation (Search for Journal in Brave)
Abstract: Flows over time generalize classical 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. In this paper, we extend this concept of a dynamic optimization problem 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 "paths" satisfying a simple switching property: Whenever two paths P and Q intersect, there must be another path that is contained in the beginning of P and the end of Q. 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 classical networks.
Full work available at URL: https://arxiv.org/abs/1211.2177
Recommendations
Cited In (3)
This page was built for publication: Abstract flows over time: a first step towards solving dynamic packing problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909560)
