Abstract
The maximum flow problem, and its dual, the minimum cut problem, are fundamental to combinatorial optimization and operations research, with applications to scheduling, VLSI layout, network routing, and transportation. In this talk I will discuss a recently discovered general technique to covert weakly approximate cut-finding algorithms into (1+epsilon)-approximate flow algorithms with only nearly-linear overhead.