A Network Simplex Framework for Discrete Unbalanced Optimal Transport
Abstract
The network simplex method is a classical algorithm for minimum cost flow problems formulated as linear programs, that has attracted recent interest from the optimal transport community. Indeed, discrete optimal transport is a subclass of minimum cost flow for which network simplex techniques compute exact solutions while leveraging the inherent problem sparsity. However, extending these approaches to other, nonlinear optimal transport formulations has yet to be thoroughly investigated. In this paper, we adapt the network simplex algorithm to unbalanced optimal transport. Our proposed framework is applicable to various unbalanced formulations, and can be implemented explicitly in the most common cases, including semiunbalanced optimal transport. The resulting algorithms are memory-efficient, and perform competitively with existing approaches, as shown by our experiments on a range of transport and barycenter calculations.
Related
- Multiscale Supervised Unbalanced Optimal Transport Flow Matching
- Existence, Equivalence, and Convergence of Unbalanced Optimal Transport
- Gaussian-Restricted Barycenters for KL-Unbalanced Optimal Transport: Variational Theory and Fixed-Point Convergence
- Dynamical Unbalanced Optimal Transport: Duality, Reachability, and Computation
- Discrete Unique Continuation on Simplex
BibTeX
@misc{agazzotti2026network,
title = {{A Network Simplex Framework for Discrete Unbalanced Optimal Transport}},
author = {Gaetano Agazzotti and Antonin Chambolle and Clément Royer},
howpublished = {HAL},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.13847},
eprint = {2610.13847},
archivePrefix = {arXiv},
url = {https://hal.science/hal-05794328v1},
note = {CC BY-NC 4.0},
}
RIS
TY - UNPB
TI - A Network Simplex Framework for Discrete Unbalanced Optimal Transport
AU - Gaetano Agazzotti
AU - Antonin Chambolle
AU - Clément Royer
PY - 2026
DA - 2026/10/09
PB - HAL
DO - 10.48550/arxiv.2610.13847
UR - https://hal.science/hal-05794328v1
AB - The network simplex method is a classical algorithm for minimum cost flow problems formulated as linear programs, that has attracted recent interest from the optimal transport community. Indeed, discrete optimal transport is a subclass of minimum cost flow for which network simplex techniques compute exact solutions while leveraging the inherent problem sparsity. However, extending these approaches to other, nonlinear optimal transport formulations has yet to be thoroughly investigated. In this paper, we adapt the network simplex algorithm to unbalanced optimal transport. Our proposed framework is applicable to various unbalanced formulations, and can be implemented explicitly in the most common cases, including semiunbalanced optimal transport. The resulting algorithms are memory-efficient, and perform competitively with existing approaches, as shown by our experiments on a range of transport and barycenter calculations.
ER -