• Alexander Barvinok, U. of Michigan

This is a survey on the structure of the transportation polytope of non-negative matrices with prescribed row and columns sums. We are interested in the following questions: What is the volume of this polytope? How many non-negative integer or 0-1 matrices with prescribed row and column sums are there? What does such a typical matrix look like? It turns out that theses questions have connections to the maximum entropy principle, the central limit theorem and the van der Waerden inequality for permanents.

• Piotr Indyk, MIT

The optimal transportation metric, a.k.a. the Earth-Mover Distance (EMD), is a popular metric widely used in theory of algorithms, computer vision, and other fields of computer science. From a computational perspective it is often convenient to represent this metric in a geometric fashion, so that efficient geometric algorithms for search, classification and other tasks can be used. Various methods for computing low-distortion representations of EMD have been developed. In this talk I will give an overview of what is known, sketch some applications, and outline several key questions that still remain open.

• Robert J. McCann, U. of Toronto

Abstract: The Monge-Kantorovich optimal transportation problem is to pair producers with consumers so as to minimize a given transportation cost. When the producers and consumers are modeled by probability densities on two given manifolds or subdomains, it is interesting to try to understand the analytical, geometric and topological features of the optimal pairing as a subset of the product manifold. This subset may or may not be the graph of a map.

This lecture describes recent developments concerning Monge's original version of this problem, and contrasts them with a capacity constrained variant in which a bound is imposed on the quantity transported between each given producer and consumer. In particular, we give a new perspective on Kantorovich's linear programming duality and expose how more subtle questions relating the structure of the solution are intimately connected to the differential topology and geometry of the chosen transportation cost.

• Adam Oberman, McGill University

(joint work with Brittany Froese and Jean-David Benamou)

The Optimal Transportation problem has been the subject of a great deal of attention by theoreticians in last couple of decades. The Wasserstein (or Earth Mover) distance allows for the metrization of the space of probability measures. As a consequence, it is now possible to more effectively measure the distance between new classes of objects. This is important in many fields, particularly in image registration, and parameter identification. However the effective computation of these distances (and the associated maps) has been intractable, except for very small (coarse) problems.

Recent advances have allowed for more efficient computation of solutions of the Monge-Kantorovich problem of optimal transportation. In the special, but important case of quadratic costs, the map can be obtained from the solution of the elliptic Monge-Ampere partial differential equation with nonstandard boundary conditions. For more general costs, the Kantorovich plan can be approximated by a finite dimensional linear program.

In this talk we will compare the cost and quality of the solutions obtained by the different methods.

In the Kantorovich Linear Programming approach, the measures are approximated by weighted sums of Dirac deltas. A direct implementation of the Kantorovich approach allows for low resolution approximations (thousands of Dirac deltas). However when the solution is known to be a map, we present a refinement to the method allows solutions to be computed at high resolutions (hundreds of thousands or more Dirac deltas). The linear programming approach has the advantage that it easily extends to more general problems: partial transportation, barycentre problems, etc. However the solutions computed are very coarse: convergence is weak (in the sense of measures) so oscillations can appear in the solutions which may require smoothing.

In the PDE approach, the measures are approximated by densities, and map is obtained as the gradient of a convex function. Convergence is stronger, since solutions are generally Lipschitz continuous, and the associated maps are more regular. On the other hand, this method requires a very specialized tools developed for the purpose, which may be more difficult to implement. However, the solution has been successfully implemented by outside groups, who have used the solver for the reflector design problem. The method has also been used (by Froese and Engquist) for parameter identification in signal recovery problems.

Together, these new methods are allowing us to extend the number of applications of the Optimal Transportation problem.