Accelerated Approximate Optimization of Multi-Commodity Flows on Directed Graphs

Li Chen, Andrei Graur, Aaron Sidford

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