A Localized Method for the Multi-commodity Flow Problem
From MaRDI portal
Abstract: This paper gives a localized method for multicommodity flow problem. We relax both the capacity constraints and the flow conservation constraints, and introduce congestion function for each edge and height function for each vertex and commodity. If the flow exceeds the capacity on an edge, the edge would have a congestion cost. If the flow into a vertex is not equal to that out of the vertex, the vertex would have a height. Based on the height function and the congestion function, a new conception, stable pseudo-flow, is introduced. Potential difference reduction algorithms, which don't rely on any shortest path or augmenting path, are designed to obtain stable pseudo-flow. If the stable pseudo-flow is a nonzero-stable pseudo-flow, there exists no feasible solution for multicommodity flow problem; if the stable pseudo-flow is a zero-stable pseudo-flow, there exists a feasible solution and the zero-stable pseudo-flow is the feasible solution. Additionally, the algorithms work in a localized manner and can be efficiently implemented in parallel, which would further improve the performance.
This page was built for publication: A Localized Method for the Multi-commodity Flow Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6505172)
