scientific article; zbMATH DE number 1127062

From MaRDI portal
Publication:4380145





Let \(X\) be a compact metric space, and let \(X_s\), \(X_b\) and \(X_{\text{constr}}\) be nonempty closed subsets of \(X\). Let \(U>0\) be fixed, and let \(\Omega\) denote the set of images of some \(\sigma\)-compact (using the uniform topology) collection of continuous functions \(x:[0,U]\to X\) satisfying \(x(0)\in X_s\), \(x(U)\in X_t\). Denoting by \({\mathcal B}\) the \(\sigma\)-field of Borel subsets of \(X\), we assume there is given a function \(P:\Omega\times{\mathcal B}\to[0,\infty)\) such that \(P(\omega,\cdot)\) is a nonnegative Borel measure on \(X\) for any \(\omega\in\Omega\) and \(P(\cdot, E)\) is a Borel measurable function on \(\Omega\) for any \(E\in{\mathcal B}\). Given a Borel measure \(\mu\) on \(\Omega\), one uses \(P\) to define a Borel measure \(\mu P\) on \(X\) bY setting \((\mu P)(E)= \int P(\omega, E) d\mu\omega\). Given a nonnegative measure \(c\) on the Borel subsets of \(X_{\text{constr}}\), one writes \(\mu P\leq c\) on \(X_{\text{constr}}\) whenever \((\mu P)(E)\leq c(E)\) holds for every Borel subset \(E\) of \(X_{\text{constr}}\). Given the preceding notation, the first main problem treated in this expository paper is finding the supremum of \(\mu(\Omega)\) as \(\mu\) ranges over all nonnegative, finite Borel measures \(\mu\) on \(\Omega\) which satisfy the constraint \(\mu P\leq c\) on \(X_{\text{constr}}\). Numerous motivating examples are given; such a measure is called a flow, the quantity \(\mu(\Omega)\) is called the strength of the flow, the kernel function \(P\) is called a static consumption scheme, and the measure \(c\) is called a static capacity constraint. The above problem is then called a static maximum-flow problem. The second main problem considered is a dynamic maximum-flow problem. Here one is given a family of kernels \(\{T_u\}_{0\leq u\leq U}\) and a family of measures \(\{c_u\}_{0\leq u\leq U}\) and finds the supremum of \(\mu(\Omega)\) as \(\mu\) ranges over all nonnegative, finite Borel measures \(\mu\) on \(\Omega\) which satisfy the constraint \(\mu T_u\leq c_u\) on \(X_{\text{constr}}\) for almost every \(u\in[0, U]\). Motivating examples are also given for the dynamic problem. The first section of the paper presents the definitions and examples. The second section shows that the dynamic problem can be reduced to the static problem. The third section sets up a dual problem. This dual problem is shown equivalent to the original problem, under the appropriate lower semicontinuity hypothesis, by use of the Hahn-Banach theorem. The fourth section describes and solves an approximation problem for the static maximum-flow problem. The fifth and final section deals with a more geometric, dual, minimum-cut problem.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4380145)