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).
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 |