Editing Maximum flow problem (section)

==History==
The maximum flow problem was first formulated in 1954 by [[Ted Harris (mathematician)|T. E. Harris]] and F. S. Ross as a simplified model of Soviet railway traffic flow.<ref name=":0">{{Cite journal | last1 = Schrijver | first1 = A. | title = On the history of the transportation and maximum flow problems | doi = 10.1007/s101070100259 | journal = Mathematical Programming | volume = 91 | issue = 3 | pages = 437–445 | year = 2002 | citeseerx = 10.1.1.23.5134 | s2cid = 10210675 }}</ref><ref>{{Cite book | doi = 10.1007/0-387-25837-X_5 | first1 =  Saul I. | last1 = Gass| first2 = Arjang A. | last2 = Assad | chapter = Mathematical, algorithmic and professional developments of operations research from 1951 to 1956 | title = An Annotated Timeline of Operations Research | series = International Series in Operations Research & Management Science | volume = 75 | pages = 79–110 | year = 2005 | isbn = 978-1-4020-8116-3 }}</ref><ref name=":2">{{cite journal | first1 = T. E. | last1 = Harris | author-link1 = Ted Harris (mathematician) | first2 = F. S. | last2 = Ross | year = 1955 | title = Fundamentals of a Method for Evaluating Rail Net Capacities | journal = Research Memorandum| url = http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf| archive-url = https://web.archive.org/web/20140108021700/http://www.dtic.mil/dtic/tr/fulltext/u2/093458.pdf| url-status = dead| archive-date = 8 January 2014}}</ref>
In 1955, [[Lester R. Ford, Jr.]] and [[D. R. Fulkerson|Delbert R. Fulkerson]] created the first known algorithm, the [[Ford–Fulkerson algorithm]].<ref name=":1">{{Cite journal | last1 = Ford | first1 = L. R. | author-link1 = L. R. Ford, Jr.| last2 = Fulkerson | first2 = D. R. | author-link2 = D. R. Fulkerson| doi = 10.4153/CJM-1956-045-5 | title = Maximal flow through a network | journal = [[Canadian Journal of Mathematics]]| volume = 8 | pages = 399–404 | year = 1956 | doi-access = free }}</ref><ref name=":3">Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press (1962).</ref> In their 1955 paper,<ref name=":1" /> Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see<ref name=":0" /> p.&nbsp;5):<blockquote>Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other.</blockquote>In their book ''Flows in Networks'',<ref name=":3" /> in 1962, Ford and Fulkerson wrote:<blockquote>It was posed to the authors in the spring of 1955 by T. E. Harris, who, in conjunction with General F. S. Ross (Ret.), had formulated a simplified model of railway traffic flow, and pinpointed this particular problem as the central one suggested by the model [11].</blockquote>where [11] refers to the 1955 secret report ''Fundamentals of a Method for Evaluating Rail net Capacities'' by Harris and Ross<ref name=":2" /> (see<ref name=":0" /> p.&nbsp;5).

Over the years, various improved solutions to the maximum flow problem were discovered, notably the shortest augmenting path algorithm of Edmonds and Karp and independently Dinitz; the blocking flow algorithm of Dinitz; the [[Push–relabel maximum flow algorithm|push-relabel algorithm]] of [[Andrew V. Goldberg|Goldberg]] and [[Robert Tarjan|Tarjan]]; and the binary blocking flow algorithm of Goldberg and Rao. The algorithms of Sherman<ref>{{Cite book | last = Sherman | first = Jonah | chapter = Nearly Maximum Flows in Nearly Linear Time | doi = 10.1109/FOCS.2013.36 | title = Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science | pages = 263–269 | year = 2013 | arxiv = 1304.2077 | isbn = 978-0-7695-5135-7 | s2cid = 14681906 }}</ref> and Kelner, Lee, Orecchia and Sidford,<ref>{{Cite book | last1 = Kelner | first1 = J. A. | last2 = Lee | first2 = Y. T. | last3 = Orecchia | first3 = L. | last4 = Sidford | first4 = A. | chapter = An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations | doi = 10.1137/1.9781611973402.16 | title = Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | pages = 217 | year = 2014 | isbn = 978-1-61197-338-9 | chapter-url = http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf | arxiv = 1304.2338 | s2cid = 10733914 | url-status = dead | archive-url = https://web.archive.org/web/20160303170302/http://math.mit.edu/~kelner/Publications/Docs/klos_maxflow_main.pdf | archive-date =2016-03-03 }}</ref><ref>{{cite web | url = http://web.mit.edu/newsoffice/2013/new-algorithm-can-dramatically-streamline-solutions-to-the-max-flow-problem-0107.html | title = New algorithm can dramatically streamline solutions to the 'max flow' problem | first = Helen | last = Knight | date = 7 January 2014 | access-date = 8 January 2014 | publisher = MIT News}}</ref> respectively, find an approximately optimal maximum flow but only work in undirected graphs.

In 2013 [[James B. Orlin]] published a paper describing an <math>O(|V| |E|)</math> algorithm.<ref name="orlin" />

In 2022 Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva published an almost-linear time algorithm running in <math>O(|E|^{1+o(1)})</math> for the [[Minimum-cost flow problem|minimum-cost flow]] problem of which for the maximum flow problem is a particular case.<ref name="almost linear" /><ref>{{Cite web |last=Klarreich |first=Erica |date=2022-06-08 |title=Researchers Achieve 'Absurdly Fast' Algorithm for Network Flow |url=https://www.quantamagazine.org/researchers-achieve-absurdly-fast-algorithm-for-network-flow-20220608/ |access-date=2022-06-08 |website=Quanta Magazine |language=en}}</ref> For the [[Single source shortest path problem|single-source shortest path (SSSP) problem]] with negative weights another particular case of minimum-cost flow problem an algorithm in almost-linear time has also been reported.<ref>{{Cite arXiv |last1=Bernstein |first1=Aaron |last2=Nanongkai |first2=Danupon |last3=Wulff-Nilsen |first3=Christian |date=2022-10-30 |title=Negative-Weight Single-Source Shortest Paths in Near-linear Time |class=cs.DS |eprint=2203.03456 }}</ref><ref>{{Cite web |last=Brubaker |first=Ben |date=2023-01-18 |title=Finally, a Fast Algorithm for Shortest Paths on Negative Graphs |url=https://www.quantamagazine.org/finally-a-fast-algorithm-for-shortest-paths-on-negative-graphs-20230118/ |access-date=2023-01-25 |website=Quanta Magazine |language=en}}</ref> Both algorithms were deemed best papers at the 2022 [[Symposium on Foundations of Computer Science]].<ref>{{Cite web |title=FOCS 2022 |url=https://focs2022.eecs.berkeley.edu/awards.html |access-date=2023-01-25 |website=focs2022.eecs.berkeley.edu}}</ref><ref>{{Cite web |last=Santosh |first=Nagarakatte |title=FOCS 2022 Best Paper Award for Prof. Aaron Bernstein's Paper |url=https://www.cs.rutgers.edu/news-events/news/news-item/focs-2022-best-paper-award-for-prof-aaron-bernstein-s-paper |access-date=2023-01-25 |website=www.cs.rutgers.edu |language=en-gb}}</ref>