An Euclidean Random Assignment Problem (ERAP in short) is as follows:
-
there are two $n$-sets $\mathcal{B}=(B_i)_{i=1}^n$ (blue points) and $\mathcal{R}=(R_i)_{I=1}^n$ (red points) of i.i.d. random variables valued on a metric space $(\Omega,D)$ according to a prob. measure $\nu$ (disorder);
-
for a permutation (or assignment) $\pi : \mathcal{B} \rightarrow \mathcal{R}$, there is an energy $\mathcal{H}(\pi)=\sum_{i=1}^n D(b_i,r_{\pi(i)})^p$, where $p\in \mathbb{R}$;
what can one say about the random variable $H_{\rm opt} = \min_\pi \mathcal{H}(\pi)$, depending on the choice of $(\Omega,D)$, on the disorder $\nu$, and $p$?
ERAPs were pioneered in statistical physics by Mézard and Parisi in the '80s as toy models for finite-dimensional spin glasses; and any ERAP is Monge-Kantorovich optimal transport problem for the empirical measures of blue and red points, in which $W_p^p(\rho_{\mathcal{B}},\rho_{\mathcal{R}})=\frac{1}{n} H_{\rm opt}$, where $W_p$ is p-Wasserstein distance.
Despite these connections, ERAPs have been exceedingly difficult to understand, and surprisingly few results have been proven to date.
In this talk I will review some selected ideas and results on ERAPs focusing on low dimensions of the underlying space $\Omega$. If time allows, I will discuss current work in progress and touch upon a few research perspectives.