full
search.png

Search

close.png

Cancel

arrow
Volume 38, Issue 6
Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach

Adam M. Oberman & Yuanlong Ruan

DOI: 10.4208/jcm.1907-m2017-0224

J. Comp. Math., 38 (2020), pp. 933-951.

Published online: 2020-06

Preview Full PDF 3264 34768

Cited by

google scholar semantic scholar
Export citation
  • 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.

  • Keywords

Optimal Transportation, Linear Programming, Monge-Kantorovich, Barycenter.

  • AMS Subject Headings

49M99, 65K15, 90C05

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address

adam.oberman@mcgill.ca (Adam M. Oberman)

ruanylpku@gmail.com (Yuanlong Ruan)

  • BibTex
  • RIS
  • TXT
@Article{JCM-38-933, author = {Oberman , Adam M. and Ruan , Yuanlong}, 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} }
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 -

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.

Oberman , Adam M. and Ruan , Yuanlong. (2020). Solution of Optimal Transportation Problems Using a Multigrid Linear Programming Approach. Journal of Computational Mathematics. 38 (6). 933-951. doi:10.4208/jcm.1907-m2017-0224
Copy to clipboard
BibteX RIS TXT
The citation has been copied to your clipboard