论文标题
独立边缘的离散最佳运输是＃p-hard
Discrete Optimal Transport with Independent Marginals is #P-Hard
论文作者
论文摘要
我们研究了评估两个k维离散随机矢量分布之间的最佳运输问题的计算复杂性。该问题的最著名算法以多项式时间运行，最大值两个分布的原子数。但是，如果两个随机矢量的组件都是独立的，那么即使问题描述的大小与K线性缩放也可以指数为K。我们证明，即使第一个随机矢量的所有组件都是独立统一的bernoulli随机变量，而第二个随机矢量仅在第二个随机矢量中，但仅仅是两个随机均可在近似artom和两个方面。我们还开发了一种动态编程型算法，该算法近似于伪多项式时间的Wasserstein距离时，当第一个随机矢量的组件遵循任意独立的离散分布，并且我们确定可以在强烈多项方面的时间上求解的特殊问题实例。
We study the computational complexity of the optimal transport problem that evaluates the Wasserstein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in the maximum of the number of atoms of the two distributions. However, if the components of either random vector are independent, then this number can be exponential in K even though the size of the problem description scales linearly with K. We prove that the described optimal transport problem is #P-hard even if all components of the first random vector are independent uniform Bernoulli random variables, while the second random vector has merely two atoms, and even if only approximate solutions are sought. We also develop a dynamic programming-type algorithm that approximates the Wasserstein distance in pseudo-polynomial time when the components of the first random vector follow arbitrary independent discrete distributions, and we identify special problem instances that can be solved exactly in strongly polynomial time.
