mg.metric geometry - How to compare finite point sets in normed spaces?

Consider the complete bipartite graph $G$ with bipartition $(A,B)$, and let the weight of an edge $ab$ be $d(a,b)$. Then $d(A,B)$ is simply the weight of a minimum weight perfect matching of $G$. Finding minimum weight perfect matchings is a well-studied problem. In particular, we can compute $d(A,B)$ in polynomial-time. Indeed, even in the case that the edge weights do not come from a metric, efficient algorithms exist. Also, even in the case that the graph is not bipartite, we can find minimum weight perfect matchings in polynomial-time. See Combinatorial Optimization, by Cook, Cunningham, Pulleyblank, and Schrijver for the sordid details.