This is a discrete version (if n is finite) of Optimal Transport. Too hairy for my feeble mind, but folks around here think it's important for fluid simulation among other things. https://en.wikipedia.org/wiki/Transportation_theory_(mathematics) On Fri, 1 Apr 2016, Veit Elser wrote:
A related question:
Suppose I have two sets of n points in R^m, A and B. How hard is it to find the bijection A -> B that minimizes the sum of squared distances?
For m=1 there’s a very efficient algorithm (your puzzle for the day), but for m>1 the best I know is solving the general minimum-weight bi-partite matching problem that grows as n^3 (for fixed m). The case where m grows with n might be interesting because a random set of points will often look quasi 1-dimensional when there are many axes to choose from.
-- Tom Duff. I'm down with the relative thingy.