• search hit 78 of 153
Back to Result List

Maximum Multicommodity Flows over Time without Intermediate Storage

Please always quote using this URN:urn:nbn:de:0296-matheon-11468
  • Flows over time generalize classical ``static'' network flows by introducing a temporal dimension. They can thus be used to model non-instantaneous travel times for flow and variation of flow values over time, both of which are crucial characteristics in many real-world routing problems. There exist two different models of flows over time with respect to flow conservation: one where flow might be stored temporarily at intermediate nodes and a stricter model where flow entering an intermediate node must instantaneously progress to the next arc. While the first model is in general easier to handle, the second model is often more realistic since in applications like, e.\,g., road traffic, storage of flow at intermediate nodes is undesired or even prohibited. The main contribution of this paper is a fully polynomial time approximation scheme (FPTAS) for (min-cost) multi-commodity flows over time without intermediate storage. This improves upon the best previously known $(2+\varepsilon)$-approximation algorithm presented 10 years ago by Fleischer and Skutella (IPCO~2002).
Metadaten
Author:Martin Groß, Martin Skutella
URN:urn:nbn:de:0296-matheon-11468
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/07/09
Release Date:2012/07/09
Tag:FPTAS; Flow over Time; Multicommodity Flow; Network Flow
Institute:Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05Cxx Graph theory (For applications of graphs, see 68R10, 81Q30, 81T15, 82B20, 82C20, 90C35, 92E10, 94C15) / 05C21 Flows in graphs
Preprint Number:969
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.