If the measures are both finite convex combinations of Dirac masses, the Kantorovich and Monge problems may be stated as linear programs, and solved using classical methods.
This insight may be used to approximate the Wasserstein distances between general measures, by first discretizing the source and target with a known level of accuracy (a difficult problem!), then computing the cost between the discrete measures.
Statement of the Discrete Problems
We suppose that and (assuming the weights and are all positive, the and are distinct, and ).
Then any transport plan for scalars (if it charged anything other than the product of the supports of and , it would not have the correct marginals).
For notation, set , , , (or more generally for generic cost functions), and denote by the vector of all ones of dimension .
Essentially, we are replacing the space with and passing from measures and functions to vectors and matrices.
With all this notation, we can say the collection of transport plans is analogous to
and the analogue of the (original) Kantorovich Problem
is just shorthand for
, an inner product on matrices).
We could define a transport map as a function , but it will be more convenient to define it as a matrix in , subject to constraints (erasing the difference between a transport map and the transport plan it defines).
We can say the collection of transport maps is
That is, a transport map corresponds to a plan which does not split mass, but instead sends all mass at
correspond to probability measures—that is,
—this is unique for a given
Then the analogue of the Monge Problem
As in the general case, this may fail to exist; in fact,
may be empty, for example if
This also has an analogue.
Useful Combinatorial Structure
The set is a closed polytope in , and since (resp. ) is a linear functional bounded below by zero on , it is quite classical (perhaps taking a compact set formed by restricting to those plans with for some fixed ) that its minimum is obtained at an extreme point.
This is also very classical.
There are other, improved methods with their own articles, like the Auction Algorithm and Sinkhorn's Algorithm.
Perhaps short descriptions/groupings of them should be put on this page to collect the information?