Speaker: Sushant Sachdeva

Date and Time: Friday, May 13, 11 am - 12 pm.

Title: Almost linear time algorithms for max-flow and more

Abstract: We give the first almost-linear time algorithmfor computing exact maximum flows and minimum-cost flows on directed graphs. Bywell known reductions, this implies almost-linear time algorithms for severalproblems including bipartite matching, optimal transport, and undirected vertexconnectivity.

Our algorithm is designed using a new Interior PointMethod (IPM) that builds the flow as a sequence of almost-linear number ofapproximate undirected minimum-ratio cycles, each of which is computed andprocessed very efficiently using a new dynamic data structure.

Our framework extends to give an almost-linear timealgorithm for computing flows that minimize general edge-separable convexfunctions to high accuracy. This gives the first almost-linear time algorithmfor several problems including entropy-regularized optimal transport, matrixscaling, p-norm flows, and Isotonic regression.

Joint work with Li Chen, Rasmus Kyng, Yang Liu, RichardPeng, and Maximilian Probst Gutenberg.