direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 712-2001

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Flows over time with load-dependent transit times
Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'02), Society of Industrial and Applied Mathematics (2002), 174-183
primary: 90C27 Combinatorial optimization
secondary: 90B20 Traffic problems
90B10 Network models, deterministic
90C35 Programming involving graphs or networks
90C25 Convex programming
05C38 Paths and cycles
05C85 Graph algorithms
90C59 Approximation methods and heuristics
68W25 Approximation algorithms
68Q25 Analysis of algorithms and problem complexity
Approximation algorithms, dynamic flow, flow over time, graph algorithms, network flow, routing, traffic models
Flow variation over time is an important feature in network flow problems arising in various applications such as road or air traffic control, production systems, communication networks (e.g., the Internet), and financial flows. Another crucial phenomenon in many of those applications is that the time taken to traverse an edge varies with the current amount of flow on this edge. Since it is already a highly nontrivial problem to map these two aspects into an appropriate and tractable mathematical network flow model, there are hardly any algorithmic techniques known which are capable of providing reasonable solutions even for networks of rather modest size.
Our work is inspired by the groundbreaking result of Ford and Fulkerson on "dynamic" s-t-flows in networks with fixed transit times on the edges and a fixed time horizon. They showed that there always exists a maximal flow over time which sends flow on certain s-t-paths at a constant rate as long as there is enough time left for the flow along a path to arrive at the sink.
Although this result does not hold for the more general setting with load-dependent transit times on the edges, we can prove that there always exists a provably good solution of this structure. Moreover, such a solution can be determined very efficiently by only one minimum convex cost flow computation on the underlying "static" network. Finally, we show that the time-dependent flow problem under consideration is NP-hard and even cannot be approximated with arbitrary precision in polynomial time, unless P=NP.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe