BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Rasmus Kyng (ETH Zürich) DTSTART:20220420T170000Z DTEND:20220420T180000Z DTSTAMP:20260423T021019Z UID:TCSPlus/39 DESCRIPTION:Title: Almost-Linear Time Algorithms for Maximum Flow and More\nby Rasmus Ky ng (ETH Zürich) as part of TCS+\n\n\nAbstract\nWe give the first almost-l inear time algorithm for computing exact maximum flows and minimum-cost fl ows on directed graphs. By well-known reductions\, this implies almost-lin ear time algorithms for several problems including bipartite matching\, op timal transport\, and undirected vertex connectivity.\n\nOur algorithm use s a new Interior Point Method (IPM) that builds the optimal flow as a sequ ence of an almost-linear number of approximate undirected minimum-ratio cy cles\, each of which is computed and processed very efficiently using a ne w dynamic data structure.\n\nOur framework extends to give an almost-linea r time algorithm for computing flows that minimize general edge-separable convex functions to high accuracy. This gives the first almost-linear time algorithm for several problems including entropy-regularized optimal tran sport\, matrix scaling\, p-norm flows\, and Isotonic regression.\n\nJoint work with Li Chen\, Yang Liu\, Richard Peng\, Maximilian Probst Gutenberg\ , and Sushant Sachdeva.\n LOCATION:https://researchseminars.org/talk/TCSPlus/39/ END:VEVENT END:VCALENDAR