Optimization seminar

Modal title

Modal content

Datum / Zeit

Referent:in

Titel

Ort

16. Mai 2022
15:00-16:30

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

Details

Titel	Maximum Flow and Minimum-Cost Flow in Almost-Linear Time
Referent:in, Affiliation	Prof. Dr. Rasmus Kyng, Dep. of Computer Science, ETH Zurich
Datum, Zeit	16. Mai 2022, 15:00-16:30
Ort	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

Hinweise: wenn Sie möchten, können Sie den iCal/ics-Kalender abonnieren.

Archiv: FS 22 FS 20 HS 19 FS 19 HS 18 FS 18 HS 17 FS 17 HS 16 FS 16 HS 15 FS 15 HS 14 FS 14 HS 13 FS 13 HS 12 FS 12 HS 11 FS 11 HS 10 FS 10 HS 09