Optimal transportation is a fundamental topic that has attracted a great
amount of attention from machine learning community in the past decades. In
this paper, we consider an interesting discrete dynamic optimal transport
problem: can we efficiently update the optimal transport plan when the weights
or the locations of the data points change? This problem is naturally motivated
by several applications in machine learning. For example, we often need to
compute the optimal transportation cost between two different data sets; if
some change happens to a few data points, should we re-compute the high
complexity cost function or update the cost by some efficient dynamic data
structure? We are aware that several dynamic maximum flow algorithms have been
proposed before, however, the research on dynamic minimum cost flow problem is
still quite limited, to the best of our knowledge. We propose a novel 2D Skip
Orthogonal List together with some dynamic tree techniques. Although our
algorithm is based on the conventional simplex method, it can efficiently
complete each pivoting operation within $O(|V|)$ time with high probability
where $V$ is the set of all supply and demand nodes. Since dynamic
modifications typically do not introduce significant changes, our algorithm
requires only a few simplex iterations in practice. So our algorithm is more
efficient than re-computing the optimal transportation cost that needs at least
one traversal over all the $O(|E|) = O(|V|^2)$ variables in general cases. Our
experiments demonstrate that our algorithm significantly outperforms existing
algorithms in the dynamic scenarios.

离散动态最优运输问题的解法，通过使用新的算法结构 2D Skip Orthogonal List 以及动态树技术，在高复杂度和动态数据结构之间找到了平衡，从而实现在数据点变化时高效更新最优运输方案。

一种新型用于动态最优运输问题的跳跃正交链表

A Novel Skip Orthogonal List for Dynamic Optimal Transport Problem

The dynamic formulation of optimal transport has attracted growing interests
in scientific computing and machine learning, and its computation requires to
solve a PDE-constrained optimization problem. The classical Eulerian
discretization based approaches suffer from the curse of dimensionality, which
arises from the approximation of high-dimensional velocity field. In this work,
we propose a deep learning based method to solve the dynamic optimal transport
in high dimensional space. Our method contains three main ingredients: a
carefully designed representation of the velocity field, the discretization of
the PDE constraint along the characteristics, and the computation of high
dimensional integral by Monte Carlo method in each time step. Specifically, in
the representation of the velocity field, we apply the classical nodal basis
function in time and the deep neural networks in space domain with the H1-norm
regularization. This technique promotes the regularity of the velocity field in
both time and space such that the discretization along the characteristic
remains to be stable during the training process. Extensive numerical examples
have been conducted to test the proposed method. Compared to other solvers of
optimal transport, our method could give more accurate results in high
dimensional cases and has very good scalability with respect to dimension.
Finally, we extend our method to more complicated cases such as crowd motion
problem.

本文提出了一种基于深度学习方法，通过蒙特卡洛方法计算动态高维空间下的最优输运问题的解法。与其他方法相比，我们的方法在更高维度下能够给出更准确的结果，并具有良好的可扩展性。

可扩展的深度学习方法求解高维动态最优输运问题

A scalable deep learning approach for solving high-dimensional dynamic optimal transport

This article reviews the use of first order convex optimization schemes to
solve the discretized dynamic optimal transport problem, initially proposed by
Benamou and Brenier. We develop a staggered grid discretization that is well
adapted to the computation of the $L^2$ optimal transport geodesic between
distributions defined on a uniform spatial grid. We show how proximal splitting
schemes can be used to solve the resulting large scale convex optimization
problem. A specific instantiation of this method on a centered grid corresponds
to the initial algorithm developed by Benamou and Brenier. We also show how
more general cost functions can be taken into account and how to extend the
method to perform optimal transport on a Riemannian manifold.

本文回顾了使用一阶凸优化方法来解决 Benamou 和 Brenier 最初提出的离散动态最优输运问题的方法，介绍了适用于计算基于均匀空间网格上定义的分布之间的 $L^2$ 最优输运测地线的交错网格离散化方法，展示了如何使用近端分裂方法来解决结果导致的大规模凸优化问题。同时，还介绍了如何考虑更一般的成本函数，以及如何扩展该方法以在 Riemann 流形上执行最优输运。