Editing Maximum flow problem (section)

==Real world applications==

===Baseball elimination===
[[File:Baseball Elimination Problem.png|thumb|Construction of network flow for baseball elimination problem]]
In the [[baseball]] elimination problem there are ''n'' teams competing in a league. At a specific stage of the league season, ''w''<sub>''i''</sub> is the number of wins and ''r''<sub>''i''</sub> is the number of games left to play for team ''i'' and ''r''<sub>ij</sub> is the number of games left against team ''j''. A team is eliminated if it has no chance to finish the season in the first place. The task of the baseball elimination problem is to determine which teams are eliminated at each point during the season. Schwartz<ref>{{Cite journal | last1 = Schwartz | first1 = B. L. | title = Possible Winners in Partially Completed Tournaments | doi = 10.1137/1008062 | journal = [[SIAM Review]]| jstor = 2028206| volume = 8 | issue = 3 | pages = 302–308 | year = 1966 | bibcode = 1966SIAMR...8..302S }}</ref> proposed a method which reduces this problem to maximum network flow. In this method a network is created to determine whether team ''k'' is eliminated.

Let ''G'' = (''V'', ''E'') be a network with {{math|''s'',''t'' ∈ ''V''}} being the source and the sink respectively. One adds a game node<sub>''ij''</sub> – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {{math|{{mset|''i'', ''j''}}}} with ''i'' < ''j'' to ''V'', and connects each of them from ''s'' by an edge with capacity ''r''<sub>''ij''</sub> – which represents the number of plays between these two teams. We also add a team node for each team and connect each game node {{math|{{mset|''i'', ''j''}}}} with two team nodes ''i'' and ''j'' to ensure one of them wins. One does not need to restrict the flow value on these edges. Finally, edges are made from team node ''i'' to the sink node ''t'' and the capacity of {{math|''w''<sub>''k''</sub> + ''r''<sub>''k''</sub> – ''w''<sub>''i''</sub>}} is set to prevent team ''i'' from winning more than {{math|''w''<sub>''k''</sub> + ''r''<sub>''k''</sub>}}.
Let ''S'' be the set of all teams participating in the league and let 
:<math>r(S - \{k\}) = \sum_{i,j \in \{S-\{k\}\} \atop i < j} r_{ij}</math>. 
In this method it is claimed team ''k'' is not eliminated if and only if a flow value of size ''r''(''S'' − {''k''}) exists in network ''G''. In the mentioned article it is proved that this flow value is the maximum flow value from ''s'' to ''t''.

===Airline scheduling===
In the airline industry a major problem is the scheduling of the flight crews. The airline scheduling problem can be considered as an application of extended maximum network flow. The input of this problem is a set of flights ''F'' which contains the information about where and when each flight departs and arrives. In one version of airline scheduling the goal is to produce a feasible schedule with at most ''k'' crews.

To solve this problem one uses a variation of the [[circulation problem]] called bounded circulation which is the generalization of [[flow network|network flow]] problems, with the added constraint of a lower bound on edge flows.

Let ''G'' = (''V'', ''E'') be a network with {{math|''s'',''t'' ∈ ''V''}} as the source and the sink nodes. For the source and destination of every flight ''i'', one adds two nodes to ''V'', node ''s''<sub>''i''</sub> as the source and node ''d''<sub>''i''</sub> as the destination node of flight ''i''. One also adds the following edges to ''E'':
# An edge with capacity [0, 1] between ''s'' and each ''s''<sub>''i''</sub>.
# An edge with capacity [0, 1] between each ''d''<sub>''i''</sub> and ''t''.
# An edge with capacity [1, 1] between each pair of ''s''<sub>''i''</sub> and ''d''<sub>''i''</sub>.
# An edge with capacity [0, 1] between each ''d''<sub>''i''</sub> and ''s''<sub>''j''</sub>, if source ''s''<sub>''j''</sub> is reachable with a reasonable amount of time and cost from the destination of flight ''i''.
# An edge with capacity [0, [[∞]]] between ''s'' and ''t''.

In the mentioned method, it is claimed and proved that finding a flow value of ''k'' in ''G'' between ''s'' and ''t'' is equal to finding a feasible schedule for flight set ''F'' with at most ''k'' crews.<ref name="ITA">{{cite book | author = [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald L. Rivest]], and [[Clifford Stein]] | title=Introduction to Algorithms, Second Edition | chapter = 26. Maximum Flow | year = 2001 | publisher = MIT Press and McGraw-Hill | isbn = 978-0-262-03293-3 | pages=643–668| title-link=Introduction to Algorithms }}</ref>

Another version of airline scheduling is finding the minimum needed crews to perform all the flights. To find an answer to this problem, a bipartite graph {{math|1={{var|G'}} = (''A'' ∪ ''B'', ''E'')}} is created where each flight has a copy in set ''A'' and set ''B''. If the same plane can perform flight ''j'' after flight ''i'', {{math|''i''∈''A''}} is connected to {{math|''j''∈''B''}}. A matching in {{mvar|G'}} induces a schedule for ''F'' and obviously maximum bipartite matching in this graph produces an airline schedule with minimum number of crews.<ref name="ITA"/> As it is mentioned in the Application part of this article, the maximum cardinality bipartite matching is an application of maximum flow problem.

===Circulation–demand problem===
There are some factories that produce goods and some villages where the goods have to be delivered. They are connected by a networks of roads with each road having a capacity {{mvar|c}} for maximum goods that can flow through it. The problem is to find if there is a circulation that satisfies the demand.
This problem can be transformed into a maximum-flow problem.
# Add a source node {{mvar|s}} and add edges from it to every factory node {{mvar|f<sub>i</sub>}} with capacity {{mvar|p<sub>i</sub>}} where {{mvar|p<sub>i</sub>}} is the production rate of factory {{mvar|f<sub>i</sub>}}.
# Add a sink node {{mvar|t}} and add edges from all villages {{mvar|v<sub>i</sub>}} to {{mvar|t}} with capacity {{mvar|d<sub>i</sub>}} where {{mvar|d<sub>i</sub>}} is the demand rate of village {{mvar|v<sub>i</sub>}}.
Let ''G'' = (''V'', ''E'') be this new network. There exists a circulation that satisfies the demand if and only if :
: {{math|Maximum flow value(''G'')}} <math> = \sum_{i \in v} d_i </math>.
If there exists a circulation, looking at the max-flow solution would give the answer as to how much goods have to be sent on a particular road for satisfying the demands.

The problem can be extended by adding a lower bound on the flow on some edges.<ref>{{Cite web|url=https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/flowext.pdf|title=Max-flow extensions: circulations with demands|last=Carl Kingsford}}</ref>

=== Image segmentation ===
[[File:Maxflow imagesegmentation image.png|thumb|Source image of size 8x8.|alt=|left|110x110px]]
[[File:Maxflow imagesegmentation network.png|thumb|Network built from the bitmap. The source is on the left, the sink on the right. The darker an edge is, the bigger is its capacity. a<sub>i</sub> is high when the pixel is green, b<sub>i</sub> when the pixel is not green. The penalty p<sub>ij</sub> are all equal.<ref>{{Cite web|url=https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow|title=Project imagesegmentationwithmaxflow, that contains the source code to produce these illustrations.|website=GitLab|language=en|url-status=dead|archive-url=https://web.archive.org/web/20191222173132/https://gitlab.com/francois.schwarzentruber/imagesegmentationwithmaxflow|archive-date=2019-12-22|access-date=2019-12-22}}</ref>]]
In their book, Kleinberg and Tardos present an algorithm for [[image segmentation|segmenting]] an image.<ref>{{Cite web|url=https://www.pearson.com/us/higher-education/program/Kleinberg-Algorithm-Design/PGM319216.html |title=Algorithm Design|website=pearson.com|language=en|access-date=2019-12-21}}</ref> They present an algorithm to find the background and the foreground in an image. More precisely, the algorithm takes a bitmap as an input modelled as follows: ''a<sub>i</sub>'' ≥ 0 is the likelihood that pixel ''i'' belongs to the foreground, ''b<sub>i</sub>'' ≥ 0 in the likelihood that pixel ''i'' belongs to the background, and ''p<sub>ij</sub>'' is the penalty if two adjacent pixels ''i'' and ''j'' are placed one in the foreground and the other in the background. The goal is to find a partition (''A'', ''B'') of the set of pixels that maximize the following quantity

:<math>q(A, B) = \sum_{i \in A} a_i + \sum_{i \in B} b_i - \sum_{\begin{matrix}i, j \text{ adjacent} \\ |A \cap \{i, j\}| = 1 \end{matrix}} p_{ij}</math>,

Indeed, for pixels in ''A'' (considered as the foreground), we gain ''a<sub>i</sub>''; for all pixels in ''B'' (considered as the background), we gain ''b<sub>i</sub>''. On the border, between two adjacent pixels ''i'' and ''j'', we loose ''p<sub>ij</sub>''. It is equivalent to minimize the quantity

:<math>q'(A, B) = \sum_{i \in A} b_i + \sum_{i \in B} a_i + \sum_{\begin{matrix}i, j \text{ adjacent} \\ |A \cap \{i, j\}| = 1 \end{matrix}} p_{ij}</math>

because

:<math>q(A, B) = \sum_{i \in A\cup B} a_i + \sum_{i \in A\cup B} b_i - q'(A, B).</math>

[[File:Maxflow imagesegmentation result.png|thumb|Minimum cut displayed on the network (triangles VS circles).]]

We now construct the network whose nodes are the pixel, plus a source and a sink, see Figure on the right. We connect the source to pixel ''i'' by an edge of weight ''a<sub>i</sub>''.  We connect the pixel ''i'' to the sink by an edge of weight ''b<sub>i</sub>''. We connect pixel ''i'' to pixel ''j'' with weight ''p<sub>ij</sub>''. Now, it remains to compute a minimum cut in that network (or equivalently a maximum flow). The last figure shows a minimum cut.