4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • 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
    Commented Dec 15, 2018 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
    Commented Dec 15, 2018 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
    Commented Dec 15, 2018 at 2:37
  • 1
    $\begingroup$ I just wonder: why close vote. $\endgroup$
    – Fedor Petrov
    Commented Dec 15, 2018 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
    Commented Dec 15, 2018 at 6:15

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

Very simple method: Bobkov-Ledoux 2020

https://projecteuclid.org/journals/annals-of-applied-probability/volume-31/issue-6/A-simple-Fourier-analytic-proof-of-the-AKT-optimal-matching/10.1214/20-AAP1656.short

and further:

https://link.springer.com/article/10.1007/s00041-020-09766-2

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .