Polynomial-Time Solvers for the Discrete $\infty$-Optimal Transport Problems

Meyer Scetbon

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…