Search Mailing List Archives


Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] [New Location] max flow in near linear time: Tomorrow, 2-4pm

Moses Charikar moses at cs.stanford.edu
Thu Mar 17 12:03:08 PDT 2022


Theory friends,

Quick reminder that Yang Liu and Li Chen will tell us about their new near
linear time max flow result *tomorrow (Fri Mar 18), 2-4pm.*

Please note the new location: *Gates 259*

Li and Yang plan to have about 30 min of slides first; the rest of the talk
will be on the whiteboard.

The room is a little smaller than our pre-pandemic theory seminar location,
with about 20 chairs and room for 30 people, so come on time!

Cheers,
Moses


On Sun, Mar 6, 2022 at 4:53 PM Moses Charikar <moses at cs.stanford.edu> wrote:

> 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/20220317/58c67883/attachment.html>


More information about the theory-seminar mailing list