Out-of-kilter algorithm
Introduction
The out-of-kilter algorithm is an algorithm that computes the solution to the minimum-cost flow problem in a flow network. It was published in 1961 by D. R. Fulkerson [1] and is described here.[2] The analog of steady state flow in a network of nodes and arcs may describe a variety of processes. Examples include transportation systems & personnel assignment actions. Arcs generally have cost & capacity parameters. A recurring problem is trying to determine the minimum cost route between two points in a capacitated network. The idea of the algorithm is to identify out-of-kilter arcs and modify the flow network until all arcs are in-kilter and a minimum cost flow has been reached.
Algorithm
To begin, the algorithm takes a single cycle and a set of node numbers. It then searches for out-of-kilter arcs. If none are found the algorithm is complete. If the flow needs to be increased or decreased to bring an arc into kilter, the algorithm will look for a path that increases or decreases the flow respectively. If no paths are found to improve the system then there is no feasible flow. This is done until all arcs are in-kilter, at which point the algorithm is complete.
Complexity
Runtime:
- The algorithm terminates within O(mU) iterations
- Dominant computation is shortest path computation
References
- ^ D. R. Fulkerson (March 1961). "An Out-of-Kilter Method for Minimal-Cost Flow Problems". Journal of the Society for Industrial and Applied Mathematics. 9 (1): 18–27. JSTOR 2099013.
- ^ Durbin, EP; Kroenke, DM (December 1967). The out-of-kilter algorithm: a primer — Memorandum RM-5472-PR (PDF). Santa Monica, California, USA: The Rand Corporation. Retrieved 2018-01-16.
External links
- Algoritmo Out-of-Kilter on YouTube (in Spanish)
 | This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it. |