Accelerated Approximate Optimization of Multi-commodity Flows on Directed Graphs

We provide m 1+o(1) kǫ -1 -time algorithms for computing multiplicative (1 -ǫ)-approximate solutions to multi-commodity flow problems with k-commodities on m-edge directed graphs, including concurrent multi-commodity flow and maximum multi-commodity flow. To obtain our results, we provide new optimization tools of potential independent interest. First, we provide an improved optimization method for solving ℓ q,p -regression problems to high accuracy. This method makes O q,p (k) queries to a high accuracy convex minimization oracle for an individual block, where O q,p (•) hides factors depending only on q, p, or poly(log m), improving upon the O q,p (k 2 ) bound of [Chen-Ye, ICALP 2024]. As a result, we obtain the first almost-linear time algorithm that solves ℓ q,p flows on directed graphs to high accuracy. Second, we present optimization tools to reduce approximately solving composite ℓ 1,∞ -regression problems to solving m o(1) ǫ -1 instances of composite ℓ q,p -regression problem. The method builds upon recent advances in solving box-simplex games [Jambulapati-Tian, NeurIPS 2023] and the area convex regularizer introduced in [Sherman, STOC 2017] to obtain faster rates for constrained versions of the problem. Carefully combining these techniques yields our directed multi-commodity flow algorithm.