Please note: This seminar will be given online.
Sushant Sachdeva, Assistant Professor
Department of Computer Science, University of Toronto
We give the first almost-linear time algorithm for computing exact maximum flows and minimum-cost flows on directed graphs. By well known reductions, this implies almost-linear time algorithms for several problems including bipartite matching, optimal transport, and undirected vertex connectivity.