Kantorovich distance on a finite metric space
From MaRDI portal
(Redirected from Publication:6318945)
Trees (05C05) Distance in graphs (05C12) Signed and weighted graphs (05C22) Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Programming involving graphs or networks (90C35)
Abstract: Kantorovich distance (or 1-Wasserstein distance) on the probability simplex of a finite metric space is the value of a Linear Programming problem for which a closed-form expression is known in some cases. When the ground distance is defined by a graph, a few examples have already been studied. In the present paper, after re-deriving, with different tools, the result for trees, we prove that, for an arbitrary weighted graph, the K-distance is the minimum of the K-distances over all the spanning trees associated with the graph. We work in the dual LP-problem by using Arens-Eells norm associated with the metric space. Finally, we introduce new norms that are naturally related to -embeddable distances and allows for a partial extension of our results to this new setting.
This page was built for publication: Kantorovich distance on a finite metric space
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6318945)
