5
$\begingroup$

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?

$\endgroup$
2
  • 2
    $\begingroup$ Take a look at this question and answer: stackoverflow.com/q/52500239/13629726 it seems very similar to your question, so there is a chance this is what you are looking for :) $\endgroup$
    – nir shahar
    Commented Aug 20, 2021 at 16:36
  • $\begingroup$ @nirshahar Thanks a lot, that's exactly it! Please consider also adding that as an answer! $\endgroup$
    – flawr
    Commented Aug 20, 2021 at 18:57

2 Answers 2

6
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Good point! However, at least intuitively it seems very likely there is some more efficient algorithm for this particular instance that relies on the properties of the distance function. $\endgroup$
    – nir shahar
    Commented Aug 20, 2021 at 19:15
3
$\begingroup$

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.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.