Multimarginal Optimal Transport (MOT) has attracted significant interest due
to applications in machine learning, statistics, and the sciences. However, in
most applications, the success of MOT is severely limited by a lack of
efficient algorithms. Indeed, MOT in general requires exponential time in the
number of marginals k and their support sizes n. This paper develops a general
theory about what "structure" makes MOT solvable in poly(n,k) time.
We develop a unified algorithmic framework for solving MOT in poly(n,k) time
by characterizing the "structure" that different algorithms require in terms of
simple variants of the dual feasibility oracle. This framework has several
benefits. First, it enables us to show that the Sinkhorn algorithm, which is
currently the most popular MOT algorithm, requires strictly more structure than
other algorithms do to solve MOT in poly(n,k) time. Second, our framework makes
it much simpler to develop poly(n,k) time algorithms for a given MOT problem.
In particular, it is necessary and sufficient to (approximately) solve the dual
feasibility oracle -- which is much more amenable to standard algorithmic
techniques.
We illustrate this ease-of-use by developing poly(n,k) time algorithms for
three general classes of MOT cost structures: (1) graphical structure; (2)
set-optimization structure; and (3) low-rank plus sparse structure. For
structure (1), we recover the known result that Sinkhorn has poly(n,k) runtime;
moreover, we provide the first poly(n,k) time algorithms for computing
solutions that are exact and sparse. For structures (2)-(3), we give the first
poly(n,k) time algorithms, even for approximate computation. Together, these
three structures encompass many -- if not most -- current applications of MOT.

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