论文标题
通过修改的匈牙利算法解决特殊类型的最佳运输问题
Solving a Special Type of Optimal Transport Problem by a Modified Hungarian Algorithm
论文作者
论文摘要
在基于Wasserstein-Distance的独立性测试中计算经验瓦斯汀的距离是具有特殊结构的最佳运输（OT）问题。该观察结果激发了我们研究一种特殊类型的OT问题，并提出了修改后的匈牙利算法以准确地解决它。对于涉及两个带有$ M $和$ n $原子（$ M \ geq n $）的边缘的OT问题，提议算法的计算复杂性为$ O（m^2n）$。在独立性测试中计算经验瓦斯汀距离需要解决这种特殊类型的OT问题，其中$ m = n^2 $。所提出的算法的相关计算复杂性为$ O（n^5）$，而应用经典的匈牙利算法的顺序为$ O（n^6）$。除了上述特殊类型的OT问题外，还表明可以采用改良的匈牙利算法来解决更广泛的OT问题。讨论了提出的算法的更广泛的应用 - 解决一对多的任务问题和多一对一的任务问题。我们进行数值实验以验证我们的理论结果。实验结果表明，提出的修改后的匈牙利算法与匈牙利算法，著名的sindhorn算法和网络单纯形算法进行了优惠相比。
Computing the empirical Wasserstein distance in the Wasserstein-distance-based independence test is an optimal transport (OT) problem with a special structure. This observation inspires us to study a special type of OT problem and propose a modified Hungarian algorithm to solve it exactly. For the OT problem involving two marginals with $m$ and $n$ atoms ($m\geq n$), respectively, the computational complexity of the proposed algorithm is $O(m^2n)$. Computing the empirical Wasserstein distance in the independence test requires solving this special type of OT problem, where $m=n^2$. The associated computational complexity of the proposed algorithm is $O(n^5)$, while the order of applying the classic Hungarian algorithm is $O(n^6)$. In addition to the aforementioned special type of OT problem, it is shown that the modified Hungarian algorithm could be adopted to solve a wider range of OT problems. Broader applications of the proposed algorithm are discussed -- solving the one-to-many assignment problem and the many-to-many assignment problem. We conduct numerical experiments to validate our theoretical results. The experiment results demonstrate that the proposed modified Hungarian algorithm compares favorably with the Hungarian algorithm, the well-known Sinkhorn algorithm, and the network simplex algorithm.
