6 Introduction with Sn standing for the set of permutations in {1,...,n}. We also see that the optimal transportation problem corresponds to finding an optimal matching between the source points xi and the target points yj. Remark. This line of reasoning fails in the continuous setting: in general, if μ and ν are absolutely continuous with respect to Lebesgue measure, there exist extremal points in Π(μ, ν) which are not concentrated on any graph. 2. Basic questions Once the above preliminaries are set, the most natural basic question is Question 1: Do there exist minimizers to the Monge-Kantorovich problem, and can one characterize them? And once a (complete or partial) answer has been given, it is natural to examine Question 2: What information on μ, ν does the knowledge of the optimal transportation cost Tc(μ, ν) bring? The answers to both questions depend heavily on the structure of the space, and on the cost function. The answer to Question 1 also depends on the “regularity” of μ, ν. Let us illustrate this on some examples, most of which will be examined again later on. It will be suﬃcient to consider the situation when X = Y = Rn, c(x, y) = |x − y|p, 0 p +∞, and μ, ν are compactly supported. • For p 1, the strict convexity of c guarantees that, if μ, ν are absolutely continuous with respect to Lebesgue measure, then there is a unique solution to the Kantorovich problem, which turns out to be also the solution to the Monge problem. The same result holds true under the weaker assumption that μ does not give positive mass to any set with finite (n − 1)-dimensional Hausdorff measure. • One can then give a geometrical characterization of the optimal maps T . For instance, in the case of a quadratic cost, p = 2, and in this case only (for n 1), these optimal maps are the (restrictions of) gradients of convex functions on Rn. In particular, they are monotone and orientation- preserving. • On the other hand, it is easy to construct measures μ, ν in Rn, which charge a “small” set (a set of Hausdorff dimension at most n − 1 in Rn, for instance a line segment in dimension 2), and such that optimal transference plans in Kantorovich’s problem have to split mass, so that solutions to the Kantorovich and Monge problems do not coincide. Worse, there will be no solution to the Monge problem!

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2003 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.