scientific article; zbMATH DE number 1127062
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.
- On one maximum multiflow problem and related metrics
- Strong Duality for the Maximum Borel Flow Problem
- scientific article; zbMATH DE number 3848938 (Why is no real title available?)
- scientific article; zbMATH DE number 3908126 (Why is no real title available?)
- scientific article; zbMATH DE number 4001832 (Why is no real title available?)
- All-maximum and all-minimum problems under some measures
- scientific article; zbMATH DE number 45022 (Why is no real title available?)
- Tight RNC approximations to max flow
- On ideal clutters, metrics and multiflows
- scientific article; zbMATH DE number 5585920 (Why is no real title available?)
- A measure-theoretical max-flow-min-cut problem
- A measure-theoretical max-flow problem
- Monge and feasibility sequences in general flow problems
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)