×

A measure-theoretical max-flow-min-cut problem. (English) Zbl 0691.90023

We investigate a measure-theoretical generalization of the famous max- flow-min-cut Theorem of Ford/Fulkerson for networks to continuous flows in bounded regions in the plane.
A flow is a measure on the set of all rectifiable Jordan curves “from the left to the right” that satisfies a certain capacity condition. The value of a flow is its total measure. We prove that the duality \(\max\)- flow\(=\min\)-cut holds, if a cut is defined as a rectifiable Jordan curve “from the bottom to the top” and the value of such a cut is the arc length of the curve weighted by the capacity.
Reviewer: W.Blum

MSC:

90B10 Deterministic network models in operations research
28A99 Classical measure theory
90C48 Programming in abstract spaces
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Anderson, E.J., Nash, P.: Linear programming in infinite-dimensional spaces. Chichester: Wiley 1987 · Zbl 0632.90038
[2] Blum, W.: Schnitte in einem ma §theoretischen Flu§maximierungsproblem. Ph. D. Thesis, Erlangen 1988
[3] Falconer, K.J.: The geometry of fractal sets. Cambridge: Cambridge University Press 1985 · Zbl 0587.28004
[4] Ford, L.R., Fulkerson, D.R.: Flows in networks. Princeton: Princeton University Press 1962 · Zbl 0106.34802
[5] Hu, T.C.: Integer programming and network flows. Massachusetts: Addison Wesley 1969 · Zbl 0197.45701
[6] Iri, M.: Theory of flows in continua as approximation to flows in networks. Survey of Math. Prog. Symp. Budapest, vol. 2, pp. 263–278, Budapest 1979
[7] Jacobs, K., Seiffert, G.: A measure-theoretical max-flow problem. Part I. Bull. Inst. Math. Acad. Sini.11, 261–280 (1983) · Zbl 0522.90027
[8] Jacobs, K.: A measure-theoretical max-flow problem. Part II, Bull. Inst. Math. Acad. Sini.12, 71–79 (1984) · Zbl 0534.90029
[9] Kellerer, H.G.: Measure-theoretic versions of linear programming. Math. Z.198, 367–400 (1988) · Zbl 0627.90067 · doi:10.1007/BF01184672
[10] Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Englewood Cliffs: Prentice-Hall 1982 · Zbl 0503.90060
[11] Philpott, A.B.: Algorithms for continuous network flow problems. Ph.D. thesis, University of Cambridge 1982 · Zbl 0498.90031
[12] Remenyi, M.: Untersuchungen über ein ma§theoretisches Schnitt-Flu§-Problem. Ph.D. Thesis, Erlangen 1986
[13] Topsoe, F.: Topology and measure (Lect. Notes Math. vol. 133) Berlin Heidelberg New York: Springer 1970 · Zbl 0197.33301
[14] Whyburn, G.T.: Topological analysis. Princeton: Princeton University Press 1964 · Zbl 0186.55901
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.