# Scalable computation of dynamic flow problems via multi-marginal graph-structured optimal transport

arXiv: https://arxiv.org/abs/2106.14485 · HTML: https://mlsanity.com/paper/2106.14485/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jun 2021.

## Built on by (most cited first, 5 of 5)

- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Estimating Latent Population Flows from Aggregated Data via Inversing Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2212.14527/) (2022)
- [Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport](https://mlsanity.com/paper/2503.09449/) (2025)
- [Fokker-Planck to Callan-Symanzik: evolution of weight matrices under training](https://mlsanity.com/paper/2501.09659/) (2025)
- [Optimal and Scalable MAPF via Multi-Marginal Optimal Transport and Schr"odinger Bridges](https://mlsanity.com/paper/2605.10917/) (2026)

## Abstract (arXiv)

In this work, we develop a new framework for dynamic network flow problems based on optimal transport theory. We show that the dynamic multi-commodity minimum-cost network flow problem can be formulated as a multi-marginal optimal transport problem, where the cost function and the constraints on the marginals are associated with a graph structure. By exploiting these structures and building on recent advances in optimal transport theory, we develop an efficient method for such entropy-regularized optimal transport problems. In particular, the graph structure is utilized to efficiently compute the projections needed in the corresponding Sinkhorn iterations, and we arrive at a scheme that is both highly computationally efficient and easy to implement. To illustrate the performance of our algorithm, we compare it with a state-of-the-art Linear programming (LP) solver. We achieve good approximations to the solution at least one order of magnitude faster than the LP solver. Finally, we showcase the methodology on a traffic routing problem with a large number of commodities.