Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms V: On a 3-Regular c-Expander the Uniform Max-Flow Is at Most 6𝒮/(c(⌊log n⌋ − 2))Research Paper
A multicommodity flow problem asks to route many source–sink demands through one capacitated network at the same time. Its min-cut (sparsest cut) is the smallest ratio, over all cuts, of the capacity crossing the cut to the demand separated by it. Routing is always limited by every cut, so the max-flow never exceeds the min-cut. For a single commodity the…