• search hit 92 of 153
Back to Result List

Generalized Maximum Flows over Time

Please always quote using this URN:urn:nbn:de:0296-matheon-10284
  • Flows over time and generalized flows are two advanced network flow models of utmost importance, as they incorporate two crucial features occurring in numerous real-life networks. Flows over time feature time as a problem dimension and allow to realistically model the fact that commodities (goods, information, etc.) are routed through a network over time. Generalized flows allow for gain/loss factors on the arcs that model physical transformations of a commodity due to leakage, evaporation, breeding, theft, or interest rates. Although the latter effects are usually time-bound, generalized flow models featuring a temporal dimension have never been studied in the literature. In this paper we introduce the problem of computing a generalized maximum flow over time in networks with both gain factors and transit times on the arcs. While generalized maximum flows and maximum flows over time can be computed efficiently, our combined problem turns out to be NP-hard and even completely non-approximable. A natural special case is given by lossy networks where the loss rate per time unit is identical on all arcs. For this case we present a (practically efficient) FPTAS that also reveals a surprising connection to so-called earliest arrival flows.

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Martin Groß, Martin Skutella
URN:urn:nbn:de:0296-matheon-10284
Referee:Rolf H. Möhring
Document Type:Preprint, Research Center Matheon
Language:English
Date of first Publication:2012/01/25
Release Date:2012/01/25
Tag:
Institute:Technische Universität Berlin
MSC-Classification:05-XX COMBINATORICS (For finite fields, see 11Txx) / 05-06 Proceedings, conferences, collections, etc.
Preprint Number:878
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.