Content deleted Content added
Edited algorithm |
Citation bot (talk | contribs) Added doi. | Use this bot. Report bugs. | Suggested by Abductive | Category:Network flow problem | #UCB_Category 6/20 |
||
| (10 intermediate revisions by 9 users not shown) | |||
Line 1:
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]]{{nnbsp}}<ref>{{cite journal |title=An Out-of-Kilter Method for Minimal-Cost Flow Problems |author=D. R. Fulkerson |journal=[[Journal of the Society for Industrial and Applied Mathematics]] |volume=9|issue=1 |date=March 1961|pages=18–27 |doi=10.1137/0109002 |jstor=2099013}}</ref> and is described here.<ref name="durbin-and-kroenke-1967">{{cite book▼
▲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]]{{nnbsp}}<ref>{{cite journal |title=An Out-of-Kilter Method for Minimal-Cost Flow Problems |author=D. R. Fulkerson |journal=[[Journal of the Society for Industrial and Applied Mathematics]] |volume=9|issue=1 |date=March 1961|pages=18–27 |jstor=2099013}}</ref> and is described here.<ref name="durbin-and-kroenke-1967">{{cite book
| last1 = Durbin | first1 = EP
| last2 = Kroenke | first2 = DM
Line 10 ⟶ 9:
| access-date = 2018-01-16
}}
</ref> 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. The algorithm can be used to minimize the total cost of a constrained flow in an oriented network.
== Algorithm ==
Line 28 ⟶ 27:
Runtime:
* The algorithm terminates within <math> O(mU) </math> iterations
* Dominant computation is shortest path computation
* Total runtime is: <math> O(m^2 U+mUn\log(n)) </math>
==References==
{{reflist|30em}}<ref>{{Cite web|url=https://www.maths.cam.ac.uk/sites/www.maths.cam.ac.uk/files/pre2014/undergrad/catam/committee/STATS/8pt4.pdf|title=Out of Kilter Algorithm|last=Cambridge|first=University of|date=July 2012|website=www.maths.cam.ac.uk}}</ref>
==External links==
Line 39:
[[Category:Network flow problem]]
| |||