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 |
