[theory-seminar] max flow in near linear time: Fri Mar 18, 2-4pm

[Moses Charikar]

Theory folks,

Mark your calendars: Our very own Yang Liu and Li Chen (visiting from
Georgia Tech) will tell us about their new breakthrough result on max flow
and min-cost flows on Friday, Mar 18, 2-4pm in Gates 415.

Title and abstract are below. Hope to see you there!

Cheers,
Moses

Title: Maximum Flow and Minimum-Cost Flow in Almost-Linear Time.

Abstract: We give an algorithm that computes exact maximum flows and
minimum-cost flows on directed graphs with $m$ edges and polynomially
bounded integral demands, costs, and capacities in $m^{1+o(1)}$ time. Our
algorithm builds the flow through a sequence of $m^{1+o(1)}$ approximate
undirected minimum-ratio cycles, each of which is computed and processed in
amortized $m^{o(1)}$ time using a dynamic data structure.

Our framework extends to an algorithm running in $m^{1+o(1)}$ time for
computing flows that minimize general edge-separable convex functions to
high accuracy. This gives an almost-linear time algorithm for several
problems including entropy-regularized optimal transport, matrix scaling,
$p$-norm flows, and isotonic regression.

Joint work with Rasmus Kyng, Richard Peng, Maximilian Probst Gutenberg, and
Sushant Sachdeva.

https://arxiv.org/abs/2203.00671
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220306/15063d3a/attachment.html>