Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms

November 1999 | TOM LEIGHTON AND SATISH RAO
This paper establishes max-flow min-cut theorems for several important classes of multicommodity flow problems. Specifically, it shows that for any $n$-node multicommodity flow problem with uniform demands, the max-flow is within an $O(\log n)$ factor of the upper bound implied by the min-cut. This result, which is existentially optimal, establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities. The paper also discusses the substantial applications of this result to the field of approximation algorithms. For example, it uses the flow result to design the first polynomial-time (polylog $n$-times-optimal) approximation algorithms for well-known NP-hard optimization problems such as graph partitioning, min-cut linear arrangement, crossing number, VLSI layout, and minimum feedback arc set. Additionally, the paper describes applications of the flow results to path routing problems, network reconfiguration, communication in distributed networks, scientific computing, and rapidly mixing Markov chains.This paper establishes max-flow min-cut theorems for several important classes of multicommodity flow problems. Specifically, it shows that for any $n$-node multicommodity flow problem with uniform demands, the max-flow is within an $O(\log n)$ factor of the upper bound implied by the min-cut. This result, which is existentially optimal, establishes an important analogue of the famous 1-commodity max-flow min-cut theorem for problems with multiple commodities. The paper also discusses the substantial applications of this result to the field of approximation algorithms. For example, it uses the flow result to design the first polynomial-time (polylog $n$-times-optimal) approximation algorithms for well-known NP-hard optimization problems such as graph partitioning, min-cut linear arrangement, crossing number, VLSI layout, and minimum feedback arc set. Additionally, the paper describes applications of the flow results to path routing problems, network reconfiguration, communication in distributed networks, scientific computing, and rapidly mixing Markov chains.
Reach us at info@study.space