Talk:Discrete Optimal Transport

Statement of the Discrete Problems

• Perhaps make this first section its own subsection called ``notation``
• Maybe instead of ``Then any transport plan`` write ``Then any transport plan is of the form... for come choiceof nonnegative weights gij
• Explain heuristically that the transport plan encodes how to rearrange mu to look like nu
• Maybe instead of ``(if it charged anything...``, make this its own sentence and write ``To see this, note that if it charged anything
• Perhaps somethign like ``For SIMPLICITY of notion``
• Before getting into the notation, explain that c(x,y) denotes the cost function (and if you want you can mention the special case of $|x-y|^{2}$)
• The last sentence is great. Consider tweaking it and making it the first sentence of this section. Perhaps ``We now describe the discrete framework. Essentially, we do this by replacing the space... vectors and matrices. In particular, we suppose that mu = sum...``

Primal Problems

• Perhaps call this ``Kantorovich's Problem and Monge's Problem``. Consider splitting into two sections.
• ``the collection of transport plans IS...`` (can drop ``analogous to``)
• state Kantorovich problem for general costs
• ``between a transport map and the CORRESPONDING transport plan it INDUCES``
• observe that transport maps are permutation matrices

Dual Problem

• Maybe add a citation?

Useful Combinatorial Structure

• Choquet's theorem ensures it admits a solution that is an extreme point (Villani p5)
• Birkhoff's theorem then ensures that these extreme points are permutation matrices, i.e. transport maps. Thus, at the discrete level, optimal solutions of Kantorovich's problem are always also optimal solutions of Monge's problem (Villani p5)

Simplex Algorithm

• Maybe add a citation to the wikipedia page?

Improved Algorithms

• Grouping them is a great idea. We can do this once there are a few more articles, so the wiki structure becomes more apparent.