Recent Advances on Maximum Flows and Minimum-Cost Flows

2022-08-10 09:00 - 10:00
Interdisciplinary Science Seminar
Title: Recent Advances on Maximum Flows and Minimum-Cost Flows

Abstract: We survey recent advances on computing flows in graphs, culminating in an almost linear time algorithm for solving minimum-cost flow and several other problems to high accuracy on directed graphs. Along the way, we will discuss intuitions from linear programming, graph theory, and data structures that influence these works, and the resulting natural open problems.

Bio: Yang P. Liu is a final-year graduate student at Stanford University. He is broadly interested in the efficient design of algorithms, particularly flows, convex optimization, and online algorithms. For his work, he has been awarded STOC and ITCS best student papers.