- search hit 1 of 1
Strong duality for the maximum Borel flow problem
Please always quote using this URN:urn:nbn:de:0296-matheon-8103
- Research on flows over time has been conducted mainly in two separate and mainly independent approaches, namely \emph{discrete} and \emph{continuous} models, depending on whether a discrete or continuous representation of time is used. Recently, Borel flows have been introduced to build a bridge between these two models. In this paper, we consider the maximum Borel flow problem formulated in a network where capacities on arcs are given as Borel measures and storage might be allowed at the nodes of the network. This problem is formulated as a linear program in a space of measures. We define a dual problem and prove a strong duality result. We show that strong duality is closely related to a MaxFlow-MinCut Theorem.
Author: | Ronald Koch, Ebrahim Nasrabadi |
---|---|
URN: | urn:nbn:de:0296-matheon-8103 |
Referee: | Martin Skutella |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2011/04/26 |
Release Date: | 2011/04/26 |
Tag: | |
Institute: | Research Center Matheon |
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 |
15-XX LINEAR AND MULTILINEAR ALGEBRA; MATRIX THEORY / 15Axx Basic linear algebra / 15A39 Linear inequalities | |
28-XX MEASURE AND INTEGRATION (For analysis on manifolds, see 58-XX) / 28Exx Miscellaneous topics in measure theory / 28E99 None of the above, but in this section | |
Preprint Number: | 778 |