Polynomial-Time Solvers for the Discrete $\infty$-Optimal Transport Problems
arXiv:2304.13467v1h-index: 11
Originality Highly original
AI Analysis
This solves a computational bottleneck in optimal transport theory, enabling faster solutions for applications in machine learning and optimization.
The paper tackles the discrete ∞-optimal transport problem by proposing polynomial-time algorithms for both Monge and Kantorovich formulations, achieving the first efficient numerical methods for these problems.
In this note, we propose polynomial-time algorithms solving the Monge and Kantorovich formulations of the $\infty$-optimal transport problem in the discrete and finite setting. It is the first time, to the best of our knowledge, that efficient numerical methods for these problems have been proposed.