Interior-point methods for multicommodity flow
November 11, 2026 (GHC 6501)

The min-cost multicommodity flow problem on a directed graph asks: given fixed (edge) capacities and costs and (vertex) demands for each of k commodities, is it possible to find a feasible flow simultaneously satisfying all demands, and if so, what is the minimum possible cost of such a flow? We demonstrate how an interior-point algorithm from Lee & Sidford 2015, combined with a recent sparse linear system solver from Kelner 2026, gives a \tilde{O}(n^{2.5}) algorithm for solving min-cost multicommodity flow on ``reasonable'' graphs. The key idea of the proof is a combinatorial transformation of the flow problem: increasing the number of variables in such a way that there are additional symmetries. We will not assume the audience has background in interior-point methods or linear system solvers.

Based on joint work with Chenxin Dai and Alicia Stepin https://arxiv.org/abs/2610.06665