In graph theory, approximate max-flow min-cut theorems concern the relationship between the maximum flow rate (max-flow) and the minimum cut (min-cut) in multi-commodity flow problems.
In these more complex scenarios, the maximum flow and the minimum cut are not necessarily equal.
For example, imagine two factories (the sources) producing different goods (the commodities) that need to be shipped to two warehouses (the sinks).
The min-cut is the smallest total road capacity that, if closed, would prevent goods from both factories from reaching their respective warehouses.
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 approximation algorithms for use in graph partition and related problems, where finding the absolute best solution is computationally prohibitive.
A "commodity" in a network flow problem is a pair of source and sink nodes.
for each i, such that the total amount of all commodities passing through any edge is no greater than its capacity.
In a multicommodity flow problem, max-flow is the maximum value of f, where f is the common fraction of each commodity that is routed, such that
units of commodity i can be simultaneously routed for each i without violating any capacity constraints.
Max-flow is always upper bounded by the min-cut for a multicommodity flow problem.
[1] In a product multicommodity flow problem, there is a nonnegative weight for each node
[1] In general, the dual of a multicommodity flow problem for a graph G is the problem of apportioning a fixed amount of weight (where weights can be considered as distances) to the edges of G such that to maximize the cumulative distance between the source and sink pairs.
Shahrokhi and Matula[4] also proved that the max-flow and min-cut are equal provided the dual of the flow problem satisfies a certain cut condition in a uniform multicommodity flow problem.
Many other researchers also showed concrete research results in similar problems[5][6][7] For a general network flow problem, the max-flow is within a factor of k of the min-cut since each commodity can be optimized separately using
[1] There are two theorems first introduced by Tom Leighton and Satish Rao in 1988[8] and then extended in 1999.
For the max-flow, the techniques from duality theory of linear programming have to be employed.
According to the duality theory of linear programming, an optimal distance function results in a total weight that is equal to the max-flow of the uniform multicommodity flow problem.
For the min-cut, a 3-stage process has to be followed:[1][6] Stage 1: Consider the dual of uniform commodity flow problem and use the optimal solution to define a graph with distance labels on the edges.
Stage 2: Starting from a source or a sink, grow a region in the graph until find a cut of small enough capacity separating the root from its mate.
[1] The proof methodology is similar to that for Theorem 2; the major difference is to take node weights into consideration.
[1] The major difference in the proof methodology compared to Theorem 2 is that, now the edge directions need to be considered when defining distance labels in stage 1 and for growing the regions in stage 2, more details can be found in.
Here below we briefly introduce a few examples, and the in-depth elaborations can be found in Leighton and Rao (1999).
Then we repeat the process then finally obtain the result that total weight of the edges in the cut is at most
It is helpful to find a layout of minimum size when designing a VLSI circuit.
in G, Chung et al.[9] defined the forwarding index of the embedding to be the maximum number of paths (each corresponding to an edge of
) that pass through any node of G. The objective is to find an embedding that minimizes the forwarding index.
-factor for every graph G. Tragoudas[10] uses the approximation algorithm for balanced separators to find a set of
It remains an open question if there is a polylog n times optimal approximation algorithm for R.[1]