2023-07-20 |
13:00-13:45 |
2023-07-20,13:00-13:45 | LR12 (A7 3F) |
07-20 Afternoon TCIS Lecture Room 12 (A7 3F)
|
Speaker |
Almost linear time algorithms for all flows Over the last decade or so, combining methods from continuous optimization and analysis with graph theoretic-insights has led to a revolution in algorithms for classic problems on graphs such as maximum flow. In this talk, I will present some of our key ideas behind our recent work that gives almost-linear time algorithms for solving all convex flow problems on graphs. This implies almost linear time algorithms for max-flow, minimum-cost flow, bipartite matching, optimal transport, matrix scaling, isotonic regression, and several other well-studied problems. Our algorithm is designed using a new Interior Point Method (IPM) that builds the flow as a sequence of almost-linear number of approximate undirected minimum-ratio cycles, each of which is computed and processed very efficiently using a new dynamic data structure. Joint work with Li Chen, Rasmus Kyng, Yang Liu, Richard Peng, and, Maximilian Probst Gutenberg.
|