论文标题
多边缘最佳运输问题的硬度结果
Hardness results for Multimarginal Optimal Transport problems
论文作者
论文摘要
多边缘最佳运输（MOT）是与固定边缘的关节概率分布相比线性编程的问题。在许多应用程序中，一个关键问题是求解MOT的复杂性：线性程序在边缘K的数量及其支撑大小n中具有指数尺寸。最近的一项工作表明，MOT是poly（n，k） - 对于某些具有poly（n，k）尺寸隐式表示的成本系族的时间。但是，目前尚不清楚这种算法研究系列可以包含哪些进一步的成本。为了理解这些基本局限性，本文启动了MOT的顽固性结果的研究。 我们的主要技术贡献是开发一种工具包，以证明NP硬度和MOT问题的不可Xibibibibility结果。我们通过使用它来确定文献中许多MOT问题的难治性来证明该工具包，这些问题已经抵制了以前的算法工作。例如，我们提供的证据表明，排斥成本可以使MOT棘手，这表明有几个此类感兴趣的问题是NP-HARD可以解决的 - 即使大约可以解决。
Multimarginal Optimal Transport (MOT) is the problem of linear programming over joint probability distributions with fixed marginals. A key issue in many applications is the complexity of solving MOT: the linear program has exponential size in the number of marginals k and their support sizes n. A recent line of work has shown that MOT is poly(n,k)-time solvable for certain families of costs that have poly(n,k)-size implicit representations. However, it is unclear what further families of costs this line of algorithmic research can encompass. In order to understand these fundamental limitations, this paper initiates the study of intractability results for MOT. Our main technical contribution is developing a toolkit for proving NP-hardness and inapproximability results for MOT problems. We demonstrate this toolkit by using it to establish the intractability of a number of MOT problems studied in the literature that have resisted previous algorithmic efforts. For instance, we provide evidence that repulsive costs make MOT intractable by showing that several such problems of interest are NP-hard to solve--even approximately.
