Consider the problem of optimally matching two measures on the circle, or
equivalently two periodic measures on the real line, and suppose the cost of
matching two points satisfies the Monge condition. We introduce a notion of
locally optimal transport plan, motivated by the weak KAM (Aubry-Mather)
theory, and show that all locally optimal transport plans are conjugate to
shifts and that the cost of a locally optimal transport plan is a convex
function of a shift parameter. This theory is applied to a transportation
problem arising in image processing: for two sets of point masses on the
circle, both of which have the same total mass, find an optimal transport plan
with respect to a given cost function satisfying the Monge condition. In the
circular case the sorting strategy fails to provide a unique candidate solution
and a naive approach requires a quadratic number of operations. For the case of
$N$ real-valued point masses we present an O(N |log epsilon|) algorithm that
approximates the optimal cost within epsilon; when all masses are integer
multiples of 1/M, the algorithm gives an exact solution in O(N log M)
operations.

研究采用局部优化运输计划的理论进行解决图像处理的问题。得到所有局部最优输运计划都与移动呈共轭关系的结论，并验证了局部最优输运计划的费用是以移动参数的凸函数。提出了一种算法可以近似优化费用，当所有质量是 1/M 的整数倍时，该算法可以在 O (NlogM) 操作中实现准确解决方案。