Faster High Accuracy Multi-Commodity Flows via Graph Techniques

Explore how graph techniques can accelerate algorithms for solving multi-commodity flow problems with high accuracy in this 45-minute lecture by Jan van der Brand from KTH Royal Institute of Technology. Delve into the unexpected application of graph structures to speed up multi-commodity flow solutions, challenging previous notions about the relationship between general linear programs and these flows. Examine the improved multi-commodity flow algorithm, discuss open problems and bottlenecks in enhancing general linear program solvers, and investigate their connections to graph problems. Gain insights into the intersection of graph theory, algorithm design, and optimization in this talk from the Simons Institute's Dynamic Graphs and Algorithm Design series.