No label defined (Q4380145)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1127062
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1127062

      Statements

      0 references
      27 August 1998
      0 references
      Borel measures
      0 references
      static maximum-flow problem
      0 references
      lower semicontinuity
      0 references
      minimum-cut problem
      0 references
      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.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references