TL;DR离散动态最优运输问题的解法，通过使用新的算法结构 2D Skip Orthogonal List 以及动态树技术，在高复杂度和动态数据结构之间找到了平衡，从而实现在数据点变化时高效更新最优运输方案。
Abstract
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 transp
本研究提出一种迭代方法来高效地解决一类严格凸代价函数的最优运输问题，该方法包括二次和 p 次幂代价函数。我们针对两个定义在离散网格上的概率分布，使用 O (n) 的存储空间和 O (n log (n)) 的操作量计算最优映射，具有近似指数收敛速度。该方法能够在几分钟内解决空间网格大小达到 4096x4096 和 384x384x384 的最优运输问题。