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: 1)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 $|Supp(f)|-1$ transports. 2) There always exists an optimal transportation plan supported in the set of edges of $X$. 3) 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.