scientific article; zbMATH DE number 3850794
Given is an oriented network \(G=(X,U)\) with a sink \(x_ 0\in X\). A non- negative number q(x) is associated with each node \(x\in X\backslash \{x_ 0\}\). The problem consists in finding a flow, \(\alpha\) : \(X\to R\), from \(x_ 0\) to other nodes (fulfilling their demands) minimizing the total cost: \[ F(\alpha)=\sum_{u\in U}\phi_ u(\alpha(u))\to \min. \] It is assumed that there are no constraints on arc capacities in the network G. The main result proved by the author is: if the cost functions \(\phi_ u(\cdot)\) are concave, non-decreasing functions then there is such a flow among the optimal flows that a part of the graph G generated by the arcs with positive flows is a tree with the root \(x_ 0\in X\). This result suggests a way of searching for a flow of minimal cost. It consists in building in G all possible trees with root \(x_ 0\) and determining a flow in each of them which is simple and univocal. Then a flow of minimal cost should be chosen. Such a procedure is the easier the smaller is the set of destinations \(Y=\{x\in X\), \(q(x)>0\}\). When \(| Y| =1\) the problem resolves itself into finding the shortest path from \(x_ 0\) to y with the lengths of arcs \(\ell(u)=\phi_ u(q(y))\), \(u\in U\). The author presents also a detailed algorithm for the case when \(| Y| =2\).
- The minimal average cost flow problem
- The minimum concave cost network flow problem with fixed numbers of sources and nonlinear arc costs
- Infinite networks: Minimal cost flows
- Fast algorithms for convex cost flow problems on circles, lines, and trees
- scientific article; zbMATH DE number 997341 (Why is no real title available?)
- Cost-volume relationship for flows through a disordered network
- scientific article; zbMATH DE number 3882168 (Why is no real title available?)
- scientific article; zbMATH DE number 3848941 (Why is no real title available?)
- scientific article; zbMATH DE number 3864952 (Why is no real title available?)
- scientific article; zbMATH DE number 3878637 (Why is no real title available?)
- A solvable routing problem
- Diagnosing Infeasibility in Min-cast Network Flow Problems Part I: Dual Infeasibility
- Flow-dependent networks: Existence and behavior at Steiner points
- Optimal Two-commodity Flows with Non-linear Cost Functions
- scientific article; zbMATH DE number 892021 (Why is no real title available?)
- Minimum cost flow in a network with an overestimated arc capacity
- Network transportation problem with concave cost functions of the flux on network edges and its applications
- Optimal flow trees for networks with general nonlinear arc costs
- Cost-minimizing networks among immiscible fluids in \({\mathbb{R}}^2\)
- The weighted linear optimal distribution problem and applications
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 Q3320095)