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.

该研究提出了在离散和有限情况下解决无穷优化运输问题的 Monge 和 Kantorovich 表述的多项式时间算法。这是我们所知道的第一次提出了这些问题的高效数值方法。

离散无穷优化输运问题的多项式时间求解器

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

This article presents a new class of distances between arbitrary nonnegative
Radon measures inspired by optimal transport. These distances are defined by
two equivalent alternative formulations: (i) a dynamic formulation defining the
distance as a geodesic distance over the space of measures (ii) a static
"Kantorovich" formulation where the distance is the minimum of an optimization
problem over pairs of couplings describing the transfer (transport, creation
and destruction) of mass between two measures. Both formulations are convex
optimization problems, and the ability to switch from one to the other
depending on the targeted application is a crucial property of our models. Of
particular interest is the Wasserstein-Fisher-Rao metric recently introduced
independently by Chizat et al. and Kondratyev et al. Defined initially through
a dynamic formulation, it belongs to this class of metrics and hence
automatically benefits from a static Kantorovich formulation.

本文介绍了一种基于最优传输的、新的非负 Radon 测度类距离，通过两个互等的、可切换的公式表述：（i）动态公式，将距离定义为测度空间上的测地距离；（ii）静态公式，距离则是一对耦合的最小化优化问题，描述了两个测量值之间的传输（运输、创造和销毁）的质量转移。两个公式都是凸优化问题，并且根据目标应用程序的不同而进行切换的能力是我们模型的关键属性。特别感兴趣的是最近由 Chizat 等和 Kondratyev 等相互独立引入的 Wasserstein-Fisher-Rao 度量，最初通过动态公式定义，属于这类度量，因此自动受益于静态 Kantorovich 公式。