Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs

Li Chen, Andrei Graur, Aaron Sidford

We provide $m^{1+o(1)}k{\epsilon }^{-1}$-time algorithms for computing multiplicative $(1-\epsilon )$-approximate solutions to multi-commodity flow problems with $k$-commodities on $m$-edge direct…