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?

  • 1
    $\begingroup$ A really interesting related problem asks a similar question for uniform weights on the edges instead. In that problem what is asked is for the minimum-cost perfect matching in the complete $n\times n$ bipartite graph $K_{n,n}$ with i.i.d. edge weights, say uniform on $[0, 1]$. Somewhat suprisingly, Aldous in 2001 showed the optimal cost converges to $\zeta(2)=\frac{\pi^2}{6}$ as $n\rightarrow \infty$. $\endgroup$ – Josiah Park Dec 15 '18 at 2:27
  • $\begingroup$ @JosiahPark Yep, I noticed the problem too, the result is really impressive, which reminds me of the $\pi$ derived from Buffon's needle problem. However, the distances between the vehicles and riders are correlated due to triangle inequality restriction, therefore, this problem might be more complicated. $\endgroup$ – Guoyang Qin Dec 15 '18 at 2:36
  • $\begingroup$ You might try to simulate things numerically, although it seems likely that someone should have considered the problem by now and written up some estimates. $\endgroup$ – Josiah Park Dec 15 '18 at 2:37
  • 1
    $\begingroup$ I just wonder: why close vote. $\endgroup$ – Fedor Petrov Dec 15 '18 at 5:38
  • 1
    $\begingroup$ @FedorPetrov Someone thinks it is "not research level" (you can see what people think by pushing the close button yourself, just do not submit your vote at the very end). I'd rather abstain from commenting further... $\endgroup$ – fedja Dec 15 '18 at 6:15

Here are two additional references you may be interested in. The methods do not require physics but a rather strong background in analysis:

-Ambrosio, Stra and Trevisan (2018), A PDE approach to a 2-dimensional matching problem.

-Ambrosio and Glaudo, finer estimates on the 2-dimensional matching problem. (Arxiv)

Furthermore, the cost function considered in these references is not the one you describe above, still this was also the case in the papers by Caracciolo et al. that you mention. If you want to consider the Euclidean distance, having a look at Talagrand's book (2014, Upper and lower bounds for stochastic processes: modern methods and classical problems) may be a good - even though not easy- introduction to the matching problems.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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