论文标题
在树上快速不平衡的最佳运输
Fast Unbalanced Optimal Transport on a Tree
论文作者
论文摘要
这项研究首次从算法的角度研究了不平衡最佳传输问题的时间复杂性。我们揭示无法有效解决不平衡最佳运输中哪些问题。具体而言，我们证明，在较强的指数时间假设下，在欧几里得公制中的Kantorovich Rubinstein距离和最佳的部分转运不能在强的亚二次时间内计算。然后，我们提出了一种算法，该算法可以在树公制上准确解决更通用的不平衡最佳传输问题。拟议的算法在不到一秒钟的时间内处理了100万个节点的树。我们的分析为不平衡最佳运输算法的理论研究构成了基础，并为不平衡的最佳运输到百万尺度数据集的应用打开了大门。
This study examines the time complexities of the unbalanced optimal transport problems from an algorithmic perspective for the first time. We reveal which problems in unbalanced optimal transport can/cannot be solved efficiently. Specifically, we prove that the Kantorovich Rubinstein distance and optimal partial transport in the Euclidean metric cannot be computed in strongly subquadratic time under the strong exponential time hypothesis. Then, we propose an algorithm that solves a more general unbalanced optimal transport problem exactly in quasi-linear time on a tree metric. The proposed algorithm processes a tree with one million nodes in less than one second. Our analysis forms a foundation for the theoretical study of unbalanced optimal transport algorithms and opens the door to the applications of unbalanced optimal transport to million-scale datasets.
