How to match two point sets to minimize total distance?

Question

Let's say we have two sets $X = \{x_1, \ldots, x_n\} \subset \mathbb R^d$, $Y =\{y_1,\ldots, y_n\} \subset \mathbb R^d$, how can we find a permutation $\pi$ such that

$$D = \sum_{i=1}^n d(x_i, y_{\pi(i)})$$

is minimal? (Here $d$ is some distance function, for simplicity we can assume it is the Euclidean distance, or maybe the squared euclidean distance.)

As far as I remember this is a well studied problem, but can anyone tell me what it is called?

Answer 1

This is an instance of the assignment problem and can be solved with standard algorithms for that problem.

Answer 2

The planer (d = 2) version of the problem is called in several names such as Euclidean bipartite matching problem, Euclidean bichromatic matching problem, or Bipartite matching of planar points. The fastest known exact algorithm in the real RAM model is the $O(n^{2+\delta})$ time ($\delta > 0$ is an arbitrary constant) algorithm due to Agarwal et al [1]. There are faster constant-factor approximation algorithms [2]. There is a sub-quadratic algorithm if the coordinates are bounded integers [3].

In general metric, the problem is also called as Earth mover's distance (EMD) or Optimal transport. Usually, EMD is formulated for a probabilistic distribution, but here we are concerned with a discrete distribution. Recently, both multiplicative and additive approximation algorithms are developed. Lahn et al [4] provide a great overview of the recent results.

• [1] Agarwal, Pankaj K., Alon Efrat, and Micha Sharir. "Vertical decomposition of shallow levels in 3-dimensional arrangements and its applications." SIAM Journal on Computing 29.3 (2000): 912-953.
• [2] Indyk, Piotr. "A near linear time constant factor approximation for Euclidean bichromatic matching (cost)." SODA. Vol. 7. 2007.
• [3] Sharathkumar, R. "A sub-quadratic algorithm for bipartite matching of planar points with bounded integer coordinates." Proceedings of the twenty-ninth annual symposium on Computational geometry. 2013.
• [4] Lahn, Nathaniel, Deepika Mulchandani, and Sharath Raghvendra. "A graph theoretic additive approximation of optimal transport." Advances in Neural Information Processing Systems (2019): 13813–13823.