Kantorovich Distance via Spanning Trees: Properties and Algorithms

In this talk, I will discuss optimal transport between probability measures supported on the same finite metric space, where the ground cost comes from a distance induced by a weighted connected graph. Building on recent work showing that the Kantorovich distance can be written as a minimum over the spanning trees of the graph, I will explain what this reformulation tells us about how to build optimal transport plans and dual potentials from the spanning tree minimising this optimization problem.

I will then show how a simple condition leads to uniqueness of the dual potential and forces a specific structure on the support of the optimal plan. Finally, I will sketch the main ideas behind the algorithms we propose to compute optimal transport plans. This is joint work with Jérémie Bigot.

Séminaire commun avec Optimal