Multimarginal Optimal Transport (MOT) has recently attracted significant interest due to its many applications. However, in most applications, the success of MOT is severely hindered by a lack of sub-exponential time algorithms. This paper develops a general theory about "structural properties" that make MOT tractable. We identify two such properties: decomposability of the cost into either (i) local interactions and simple global interactions; or (ii) low-rank interactions and sparse interactions. We also provide strong evidence that (iii) repulsive costs make MOT intractable by showing that several such problems of interest are NP-hard to solve--even approximately. These three structures are quite general, and collectively they encompass many (if not most) current MOT applications. We demonstrate our results on a variety of applications in machine learning, statistics, physics, and computational geometry.

本论文提出了一种通用的理论框架和算法，通过利用简单的变形来解决多边际最优输运问题（MOT）在多项式时间内，尤其是解决了当前最流行的 Sinkhorn 算法对于 MOT 求解在多项式时间内所需要的额外结构，提供了新的精确且稀疏的算法，同时对于三种 MOT 成本结构提供了可充分利用标准算法技术的多项式时间算法。

带结构的多边际最优传输问题的多项式时间算法