imported>Shocksingularity: Adding short description: "Algorithm in graph theory"

2025-12-12T02:37:57Z

Adding short description: "Algorithm in graph theory"

New page

{{Short description|Algorithm in graph theory}}
In [[mathematical optimization]], the '''network simplex algorithm''' is a [[graph theory|graph theoretic]] specialization of the [[simplex algorithm]]. The algorithm is usually formulated in terms of a [[minimum-cost flow problem]]. The network simplex method works very well in practice, typically 200 to 300 times faster than the simplex method applied to general linear program of same dimensions.<ref>{{Cite book | last1=Bazaraa | first1=Mokhtar S. | last2=Jarvis | first2=John J. | last3=Sherali | first3=Hanif D. | year=2010 | title=Linear Programming and Network Flows | edition=4th | publisher=Wiley | page=453}}</ref>

== History ==
For a long time, the existence of a provably efficient network simplex algorithm was one of the major open problems in complexity theory, even though efficient-in-practice versions were available. In 1995 [[James B. Orlin|Orlin]] provided the first polynomial algorithm with runtime of <math>O(V^2 E \log(VC))</math> where <math>C</math> is maximum cost of any edges.<ref>{{Cite journal|title = A polynomial time primal network simplex algorithm for minimum cost flows|journal = Mathematical Programming|date = 1997-08-01|issn = 0025-5610|pages = 109–129|volume = 78|issue = 2|doi = 10.1007/BF02614365|first = James B.|last = Orlin|hdl = 1721.1/2584|s2cid = 3107792|hdl-access = free}}</ref> Later [[Robert Tarjan|Tarjan]] improved this to <math>O(VE \log V \log(VC))</math> using [[dynamic trees]] in 1997.<ref>{{Cite journal|title = Dynamic trees as search trees via euler tours, applied to the network simplex algorithm|journal = Mathematical Programming|date = 1997-08-01|issn = 0025-5610|pages = 169–177|volume = 78|issue = 2|doi = 10.1007/BF02614369|first = Robert E.|last = Tarjan|s2cid = 18977577}}</ref> Strongly polynomial dual network simplex algorithms for the same problem, but with a higher dependence on the numbers of edges and vertices in the graph, have been known for longer.<ref>{{citation
| last1 = Orlin | first1 = James B. | author1-link = James B. Orlin
| last2 = Plotkin | first2 = Serge A.
| last3 = Tardos | first3 = Éva | author3-link = Éva Tardos
| date = June 1993
| doi = 10.1007/bf01580615
| issue = 1–3
| journal = [[Mathematical Programming]]
| pages = 255–276
| title = Polynomial dual network simplex algorithms
| volume = 60| citeseerx = 10.1.1.297.5730 | s2cid = 5838223 }}</ref>

== Overview ==
The network simplex method is an adaptation of the bounded variable primal simplex algorithm. The basis is represented as a rooted spanning tree of the underlying network, in which variables are represented by arcs, and the simplex multipliers by node potentials. At each iteration, an entering variable is selected by some pricing strategy, based on the dual multipliers (node potentials), and forms a cycle with the arcs of the tree. The leaving variable is the arc of the cycle with the least augmenting flow. The substitution of entering for leaving arc, and the reconstruction of the tree is called a pivot. When no non-basic arc remains eligible to enter, the optimal solution has been reached.

== Applications ==
The network simplex algorithm can be used to solve many practical problems including,<ref>{{Cite book|title = Linear Programming|last = Chvatal|first = Vasek|publisher = Macmillan|year = 1983|isbn = 9780716715870|pages = [https://archive.org/details/linearprogrammin00chv/page/320 320–351]|chapter = 20|chapter-url = https://books.google.com/books?id=DN20_tW_BV0C&dq=network%20simplex%20applications&pg=PA320|url = https://archive.org/details/linearprogrammin00chv/page/320}}</ref>
* [[Transshipment problem]]
* [[Transportation theory (mathematics)|Hitchcock transportation problem]]
* [[Assignment problem]]
* Chains and antichains in [[partially ordered set]]s
* [[System of distinct representatives]]
* Covers and matching in [[bipartite graph]]s
* Caterer problem

==References==
{{Reflist}}

== External links ==
* [http://www.4er.org/CourseNotes/Book%20B/B-IV.pdf Solving Network Problems] {{Webarchive|url=https://web.archive.org/web/20150526071642/http://www.4er.org/CourseNotes/Book%20B/B-IV.pdf |date=2015-05-26 }} Section 14, p B-113 shows an example execution

[[Category:Optimization algorithms and methods]]
[[Category:Linear programming]]
[[Category:Network flow problem]]
[[Category:Mathematical problems]]
[[Category:Network theory]]
[[Category:Polynomial-time problems]]
[[Category:Graph algorithms]]
[[Category:Computational problems in graph theory]]

Network simplex algorithm - Revision history

imported>Shocksingularity: Adding short description: "Algorithm in graph theory"