Abstract
In this talk, we will see that graph techniques can speed up algorithms for solving multi-commodity flow to high accuracy. This is unexpected as it was shown in [Ita'79 and Ding-Kyng-Zhang'22] that general linear programs without any graph structure can be reduced to multi-commodity flows.
In addition to outlining our improved multi-commodity flow algorithm, we will see open problems and bottlenecks for improving general linear program solvers and how they connect to graph problems.