Numerical and analytical results for the transportation problem of Monge-Kantorovich

The Monge-Kantorovich transportation problem has a long and interesting history and has found a great variety of applications (see Rachev and Rüschendorf (1998a,b)). Some interesting characterizations of optimal solutions to the transportation problem (resp. coupling problems) have been found recently. For the squared distance and discrete distributions they relate optimal solutions to generalized Voronoi diagrams. Numerically we investigate the dependence of optimal couplings on variations of the coupling function. Numerical results confirm also a conjecture on optimal couplings in the one-dimensional case for nonconvex coupling functions. A proof of this conjecture is given under some technical conditions. Received: November 1999