Yang Liu: Lessons on Algorithmic Graph Theory from Maxflow

PASSCODE: 728726

There has been a flurry of recent progress on the maximum flow and min-cost flow problems, resulting in an almost-linear time for both problems and generalizations. What can we learn about general algorithm design from the techniques used in maxflow algorithms? At a high level, recent algorithms for maximum flow share several key pieces: an outer loop to build the maximum flow from simpler subproblems, and a method for solving the subproblem using techniques such as vertex reductions, edge sparsification, and connections to dynamic data structures. I will discuss the exciting past, present, and future research directions that each of these components motivate.