Skip to main content
4 of 5
deleted 302 characters in body

What is the expected minimum total matching distance between two partitions of identically and independently distributed points?

Bipartite matching

Suppose a square $[0,1]\times [0,1]$ in which $N$ vehicles $V_i$ and $N$ riders $R_i$ are distributed identically and independently (say, uniform distribution), a bipartite matching (or a permutation, $\pi(i)$) is done between the vehicles and riders with the objective that the total distance

$$Z=\min_{\pi}\sum_1^N \sqrt{\Vert V_{\pi(i)}-R_i\Vert^2}$$

is minimized.

Since the locations of vehicles and riders are distributed randomly, therefore $Z$ is a random variable. The expectation of $Z$ is thus of interest. The question is how to derive the $E(Z)$.

I have found some related papers, such as

  1. Caracciolo, S., & Sicuro, G. (2015). Quadratic stochastic Euclidean bipartite matching problem. Physical review letters, 115(23), 230601.
  2. Boniolo, E., Caracciolo, S., & Sportiello, A. (2014). Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle. Journal of Statistical Mechanics: Theory and Experiment, 2014(11), P11023.

I am trying to read them to figure out how, but their derivation all has some part heavily related to physics and statistical mechanics, which makes me struggle to understand it but I fail.

I was wondering if there is a version with a no-physics-just-operations-research flavor to solve this problem?