![Pets flow](https://upload.wikimedia.org/wikipedia/commons/2/2f/Pets_flow.svg)
In
optimization theory
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, maximum flow problems involve finding a feasible flow through a
flow network
In graph theory, a flow network (also known as a transportation network) is a directed graph where each edge has a capacity and each edge receives a flow. The amount of flow on an edge cannot exceed the capacity of the edge. Often in operations res ...
that obtains the maximum possible flow rate.
The maximum flow problem can be seen as a special case of more complex network flow problems, such as the
circulation problem The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special node ...
. The maximum value of an s-t flow (i.e., flow from
source
Source may refer to:
Research
* Historical document
* Historical source
* Source (intelligence) or sub source, typically a confidential provider of non open-source intelligence
* Source (journalism), a person, publication, publishing institute o ...
s to
sink
A sink is a bowl-shaped plumbing fixture for washing hands, dishwashing, and other purposes. Sinks have a tap (faucet) that supply hot and cold water and may include a spray feature to be used for faster rinsing. They also include a drain to ...
t) is equal to the minimum capacity of an
s-t cut (i.e., cut severing s from t) in the network, as stated in the
max-flow min-cut theorem
In computer science and optimization theory, the max-flow min-cut theorem states that in a flow network, the maximum amount of flow passing from the ''source'' to the ''sink'' is equal to the total weight of the edges in a minimum cut, i.e., the ...
.
History
The maximum flow problem was first formulated in 1954 by
T. E. Harris and F. S. Ross as a simplified model of Soviet railway traffic flow.
In 1955,
Lester R. Ford, Jr. and
Delbert R. Fulkerson created the first known algorithm, the
Ford–Fulkerson algorithm.
[Ford, L.R., Jr.; Fulkerson, D.R., ''Flows in Networks'', Princeton University Press (1962).] In their 1955 paper,
Ford and Fulkerson wrote that the problem of Harris and Ross is formulated as follows (see
p. 5):
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.
In their book ''Flows in Network'',
in 1962, Ford and Fulkerson wrote:
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 1
where
1refers to the 1955 secret report ''Fundamentals of a Method for Evaluating Rail net Capacities'' by Harris and Ross
(see
p. 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 algorithm of
Goldberg Goldberg or Goldberger may refer to:
Arts and entertainment
* Goldberg Ensemble, a British string ensemble
* ''Goldberg Variations'', a set of 30 keyboard variations by Johann Sebastian Bach
* ''The Goldbergs (broadcast series)'', American radio ...
and
Tarjan; and the binary blocking flow algorithm of Goldberg and Rao. The algorithms of Sherman and Kelner, Lee, Orecchia and Sidford, respectively, find an approximately optimal maximum flow but only work in undirected graphs.
In 2013
James B. Orlin published a paper describing an
algorithm.
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
.
Definition
![Simpe_flow_network](https://upload.wikimedia.org/wikipedia/commons/f/f6/Simpe_flow_network.svg)
First we establish some notation:
* Let
be a network with
being the source and the sink of
respectively.
* If
is function on the edges of
then its value on
is denoted by
or
Definition. The capacity of an edge is the maximum amount of flow that can pass through an edge. Formally it is a map
Definition. A flow is a map
that satisfies the following:
*''Capacity constraint''. The flow of an edge cannot exceed its capacity, in other words:
for all
* ''Conservation of flows.'' The sum of the flows entering a node must equal the sum of the flows exiting that node, except for the source and the sink. Or:
::
''Remark''. Flows are skew symmetric:
for all
Definition. The value of flow is the amount of flow passing from the source to the sink. Formally for a flow
it is given by:
:
Definition. The maximum flow problem is to route as much flow as possible from the source to the sink, in other words find the flow
with maximum value.
Note that several maximum flows may exist, and if arbitrary real (or even arbitrary rational) values of flow are permitted (instead of just integers), there is either exactly one maximum flow, or infinitely many, since there are infinitely many linear combinations of the base maximum flows. In other words, if we send
units of flow on edge
in one maximum flow, and
units of flow on
in another maximum flow, then for each