Numerical and analytical results for the transportation problem of Monge-Kantorovich. (English) Zbl 1016.60017

Rüschendorf, Ludger; Uckelmann, Ludger

Metrika 51, No. 3, 245-258 (2000).

Summary: The Monge-Kantorovich transportation problem has a long and interesting history and has found a great variety of applications [see S. T. Rachev and L. Rüschendorf, “Mass transportation problems”. Vol. 1, 2 (New York, 1998)]. 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.

MSC:

60E05	Probability distributions: general theory
60A10	Probabilistic measure theory
90C15	Stochastic programming
28A35	Measures and integrals in product spaces

Keywords:

Monge-Kantorovich transportation problem; characterizations of optimal solutions; generalized Voronoi digrams; optimal couplings

Citations:

Zbl 0990.60500

Software:

SoPlex