A pipeline network's maximum throughput, a settlement network's maximum simultaneously-clearable payment volume, and the maximum number of buy orders that can be matched against sell orders are all instances of the maximum flow problem: given a network with edge capacities, how much "stuff" can be pushed from a source to a sink at once? This note builds the Ford-Fulkerson method via augmenting paths, proves the celebrated max-flow min-cut theorem (a genuine duality result, in the same spirit as this vault's other optimality certificates), and shows how bipartite matching — a problem that looks unrelated on the surface — reduces directly to a flow instance.
In this lesson
- Learning objectives
- Flow networks
- The Ford-Fulkerson method
- The max-flow min-cut theorem
- Bipartite matching
Before you start
The full lesson, with worked examples and exercise solutions, is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or explore the curriculum.