Let $(X,d)$ be a metric space and $Fin(X)$ be the family of all non-empty finite subsets of $X$. For every $n\in\mathbb N$ the elements of the power $X^n$ are thought as functions $f:n\to X$ where $n:=\{0,\dots,n-1\}$. For such function $f$ its image $f(n)\subset X$ will be denoted by $rg(f)$.
For every $p\in[1,\infty]$ the space $X^n$ is endowed with the $\ell_p$-metric $d_p$ defined by $$d_p(f,g)=\begin{cases}\sqrt[p]{\sum_{i\in n}d(f(i),g(i))^p}& \mbox{if $p<\infty$;}\\ \;\;\max_{i\in n}d(f(i),g(i))&\mbox{if $p=\infty$.} \end{cases} $$
I am interested in the metric $d_p$ on the hyperspace $Fin(X)$, defined by the formula$$d_p(A,B):=\inf\sum_{i=0}^kd_p(f_i,g_i)$$ where the infimum is taken over all chains $(f_0,g_0),\dots,(f_k,g_k)\in\bigoplus_{n\in\mathbb N}X^n\times X^n$ such that $A=rg(f_0)$, $B=rg(g_k)$ and $rg(g_i)=rg(f_{i+1})$ for all $i<k$.
The metric $d_p$ can be equivalently defined as the largest metric on $Fin(X)$ such that for every $n\in\mathbb N$ the map $X^n\to Fin(X)$, $(x_1,\dots,x_n)\mapsto\{x_1,\dots,x_n\}$, is non-expanding with respect to the $\ell_p$-metric on $X^n$.
It can be shown that the distance $d_\infty$ on $Fin(X)$ coincides with the well-known Hausdorff metric. I am interested in the metrics $d_p$ on $Fin(X)$ for $p<\infty$, especially in the metric $d_1$ on $Fin(X)$.
The distance $d_1$ can have applications in economics as it represent the cost of transportation of goods whose mass is negligible comparing to the mass of the transporting car.
For the metric $d_1$ many natural problems appear. In particular:
Problem. Find an (efficient) algorithm for calculating the distance $d_1(A,B)$ between two finite subsets $A,B$ of $\mathbb R^n$ (for $n=1$ this problem has been resolved here).
Have such problems been studied in mathematical or economical literature?
Remark 1. In the simplest case of the 2-element set $\{a,b\}$ and a 1-element set $\{c\}$ in the plane the distance $d_1(\{a,b\},\{c\})=\|a-t\|+\|b-t\|+\|c-t\|$ where $t$ is the Fermat-Toricelli point of the triangle $\{a,b,c\}$, and $\|\cdot\|$ is the standard Euclidean norm on the plane.
Remark 2. It seems that for arbitrary finite sets $A,B$ in the plane the distance $d_1(A,B)$ is equal to the smallest total length of edges of a graph $\Gamma\subset\mathbb R^2$ whose any connected component intersects both sets $A$ and $B$.
The problem of finding such graph $\Gamma$ is related to the classical Steiner tree problem which is known to be difficult (at least, NP-hard), so the problem of calculating the distance $d_1$ on $Fin(\mathbb R^2)$ is also hard.
But maybe for the real line or for the Urysohn universal metric space $\mathbb U$ this problem is computationally more simple? In the latter case the distance $d_1$ between two finite subsets of $A,B$ of $\mathbb U$ depends only on the restriction of the metric to $A\cup B$ and hence depends on finite number of real parameters; so, in principle, is computable.
Remark 3. It seems that the completion of the metric space $(Fin(\mathbb R),d_1)$ can be identified with the space of all compact subsets of zero Lebesgue measure on the real line.
