On the transportation cost norm on finite metric graphs

Abstract

For a finite metric graph $X=(V,E,\ell )$, where $V$ is endowed with the shortest path metric, we consider the transportation cost problem associated with the distance $d$ on $V$. Namely, for $f$ a function with total sum $0$ on $V$, write $f={\sum }_{a,b\in V}P(a,b)({\delta }_a-{\delta }_b)$, where the transportation plan $P$ satisfies $P(a,b)\ge 0$ for $(a,b)\in V\times V$. The cost of $P$ is $W(P):={\sum }_{a,b\in V}P(a,b)d(a,b)$ and the transportation norm of $f$ is $\Vert f{\Vert }_{TC}={\min }_{P}W(P)$, where $P$ runs over all transportation plans for $f$.
In this semi-survey paper, we give short proofs for the following statements:

• There always exists an optimal transportation plan supported in $V_{+}\times V_{-}$, where $V_{+}=\{x\in V:f(x)>0\}$ and $V_{-}=\{x\in V:f(x)<0\}$. If $X$ is a metric tree, we may moreover assume that this plan involves at most $|\mathrm{Supp}(f)|-1$ transports.
• There always exists an optimal transportation plan supported in the set of edges of $X$.
• Better, there always exists an optimal transportation plan supported in some spanning tree of $X$.

We use this to reprove known formulae for the transportation norm when $X$ is either a tree or a cycle.