TY - JOUR
T1 - Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach
AU - Oberman , Adam M.
AU - Ruan , Yuanlong
JO - Journal of Computational Mathematics
VL - 6
SP - 933
EP - 951
PY - 2020
DA - 2020/06
SN - 38
DO - http://doi.org/10.4208/jcm.1907-m2017-0224
UR - https://global-sci.org/intro/article_detail/jcm/16974.html
KW - Optimal Transportation, Linear Programming, Monge-Kantorovich, Barycenter.
AB - <p style="text-align: justify;">We compute and visualize solutions to the Optimal Transportation (OT) problem for
a wide class of cost functions. The standard linear programming (LP) discretization of
the continuous problem becomes intractable for moderate grid sizes. A grid refinement
method results in a linear cost algorithm. Weak convergence of solutions is established and
barycentric projection of transference plans is used to improve the accuracy of solutions.
Optimal maps between nonconvex domains, partial OT free boundaries, and high accuracy
barycenters are presented.</p>