Optimization seminar

Modal title

Modal content

Date / Time

Speaker

Title

Location

16 May 2022
15:00-16:30

Prof. Dr. Rasmus Kyng
Dep. of Computer Science, ETH Zurich

Event Details

Title	Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Speaker, Affiliation	Prof. Dr. Rasmus Kyng, Dep. of Computer Science, ETH Zurich
Date, Time	16 May 2022, 15:00-16:30
Location	HG G 19.2
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 m1+o(1) time. Our algorithm builds the flow through a sequence of m1+o(1) approximate undirected minimum-ratio cycles, each of which is computed and processed in amortized mo(1) time using a new dynamic graph data structure. Our framework extends to algorithms running in m1+o(1) time for computing flows that minimize general edge-separable convex functions to high accuracy. This gives almost-linear time algorithms for several problems including entropy-regularized optimal transport, matrix scaling, p-norm flows, and p-norm isotonic regression on arbitrary directed acyclic graphs.

Maximum Flow and Minimum-Cost Flow in Almost-Linear Timeread_more

Note: if you want you can subscribe to the iCal/ics Calender.

Archive: SS 22 SS 20 AS 19 SS 19 AS 18 SS 18 AS 17 SS 17 AS 16 SS 16 AS 15 SS 15 AS 14 SS 14 AS 13 SS 13 AS 12 SS 12 AS 11 SS 11 AS 10 SS 10 AS 09