Approximate Max-Flow Min-Cut Theorem

In graph theory, approximate max-flow min-cut theorems describe the relationship between the maximum flow rate and the minimum cut in multi-commodity flow networks, where several distinct commodities share the same infrastructure. The classical max-flow min-cut theorem guarantees exact equality between maximum flow and minimum cut for a single commodity, but that equality fails once multiple commodities compete for the same edges. Tom Leighton and Satish Rao introduced bounds in 1988, later extended in 1999, showing how close the maximum multi-commodity flow can get to the minimum cut, with the flow never exceeding the cut. These bounds underlie approximation algorithms for graph partitioning problems that are otherwise computationally difficult to solve exactly.