Approximate max-flow min-cut theorem

In <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a>, approximate max-flow min-cut theorems concern the relationship between the maximum flow rate (<a href="/facts/Maximum_flow_problem/aSal0FGF">max-flow</a>) and the minimum cut (<a href="/facts/Minimum_cut/xWTNp1hN">min-cut</a>) in <a href="/facts/Multi-commodity_flow_problem/xdWBWmqa">multi-commodity flow problems</a>. The classic <a href="/facts/Max-flow_min-cut_theorem/qrXp2ut7">max-flow min-cut theorem</a> states that for networks with a single type of flow (single-commodity flows), the maximum possible flow from source to <a href="/facts/Sink_(computing)/2dQSlLcE">sink</a> is precisely equal to the capacity of the smallest cut. However, this equality doesn't generally hold when multiple types of flow exist in the network (multi-commodity flows). In these more complex scenarios, the maximum flow and the minimum cut are not necessarily equal. Instead, approximate max-flow min-cut theorems provide bounds on how close the maximum flow can get to the minimum cut, with the max-flow always being lower or equal to the min-cut.
For example, imagine two factories (the sources) producing different goods (the commodities) that need to be shipped to two warehouses (the sinks). Each road has a capacity limit for all goods combined. The min-cut is the smallest total road capacity that, if closed, would prevent goods from both factories from reaching their respective warehouses. The max-flow is the maximum total amount of goods that can be shipped. Because both types of goods compete for the same roads, the max-flow may be lower than the min-cut. The approximate max-flow min-cut theorem tells us how close the maximum amount of shipped goods can get to that minimum road capacity.
The theorems have enabled the development of <a href="/facts/Approximation_algorithm/BWlf7M32">approximation algorithms</a> for use in <a href="/facts/Graph_partition/MSQF0WyD">graph partition</a> and related problems, where finding the absolute best solution is computationally prohibitive.

Approximate max-flow min-cut theorem open-in-new

Approximate max-flow min-cut theorem