Efficient optimal transport in 1D: not as trivial as it may seem

We consider two problems of optimal transportation in 1D: (i) optimal matching of two measures on the circle with the cost c(x, y) of matching two points x,y that has a certain convexity property (the Monge condition), and (ii) optimal matching on the line for a concave-type cost satisfying an opposite condition.
An optimal matching algorithm in the first case is based on a construction inspired by the weak KAM theory, which reveals a particular convex structure of this problem. In the second case, an algorithm employs a non-obvious submodularity structure.
Applications to image processing are discussed.
This is a joint work with Julie Delon (Télécom Paris) and Julien Salomon (Université Paris-Dauphine/CEREMADE).