Faster high-accuracy multicommodity flow in dense graphs

Chenxin Dai, Alicia Stepin, Colin Tang

We give a fast algorithm for solving min-cost $k$-commodity flow. The basic idea is to construct an auxiliary linear program that has low rank and whose minimum value is at most $1…