direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Logo der TU Berlin

Inhalt des Dokuments

Preprint 757-2002

Combinatorial Optimization & Graph Algorithms group (COGA-Preprints)

Minimum Cost Flows Over Time without Intermediate Storage
Lisa Fleischer and Martin Skutella
In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'03), Society of Industrial and Applied Mathematics (2003), to appear.
primary: 90C27 Combinatorial optimization
secondary: 90B10 Network models, deterministic
90C35 Programming involving graphs or networks
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
Flows over time (also called dynamic flows) generalize standard network flows by introducing an element of time. They naturally model problems where travel and transmission are not instantaneous. Solving these problems raises issues that do not arise in standard network flows. One issue is the question of storage of flow at intermediate nodes. In most applications (such as, e.g., traffic routing, evacuation planning, telecommunications etc.), intermediate storage is limited, undesired, or prohibited.
The minimum cost flow over time problem is NP-hard. In this paper we 1) prove that the minimum cost flow over time never requires storage; 2) provide the first approximation scheme for minimum cost flows over time that does not require storage; 3) provide the first approximation scheme for minimum cost flows over time that meets hard cost constraints, while approximating only makespan.
Our approach is based on a condensed variant of time-expanded networks. It also yields fast approximation schemes with simple solutions for the quickest multicommodity flow problem.
Finally, using completely different techniques, we describe a very simple capacity scaling FPAS for the minimum cost flow over time problem when costs are proportional to transit times. The algorithm builds upon our observation about the structure of optimal solutions to this problem: they are universally quickest flows. Again, the FPAS does not use intermediate node storage. In contrast to the preceding algorithms that use a time-expanded network, this FPAS runs directly on the original network.
Download as [PDF] [ps.gz]
Title: Source

Zusatzinformationen / Extras


Schnellnavigation zur Seite über Nummerneingabe