@Article{JCM-38-933, author = {Adam M. and Oberman and adam.oberman@mcgill.ca and 7826 and Department of Mathematics, McGill University, Montreal, Canada and Adam M. Oberman and Yuanlong and Ruan and ruanylpku@gmail.com and 7827 and Department of Mathematics, Beihang University, Beijing, China and Yuanlong Ruan}, title = {Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach}, journal = {Journal of Computational Mathematics}, year = {2020}, volume = {38}, number = {6}, pages = {933--951}, abstract = {

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.

}, issn = {1991-7139}, doi = {https://doi.org/10.4208/jcm.1907-m2017-0224}, url = {http://global-sci.org/intro/article_detail/jcm/16974.html} }