Euclidean Random Assignment Problems

In brief: given \( 2n \) points, \(n\) “reds” and \(n\) “blues” in a Euclidean space, solving the associated Euclidean Assignment Problem consists in finding the bijection between red and blue points that minimizes a functional of the distances of the point positions (an example instance at \(n=500\) on the unit square is depicted in figure). In the simplest stochastic version of this problem, the points are a binomial process, and some interest has developed over the years on the typical properties of the solution in the limit \( n \to \infty \) depending on the dimension of the ambient space and choice of cost function. The main motivations come by an analogy of this problem with a low-dimensional disordered-system and by recent results on the Monge–Kantorovich optimal transport problem.

Keywords: random assignment problem, statistical field theory, disordered systems in finite dimension, Monge-Kantorovich transportation problem –>

If you are interested in numerical simulations, you may want to have a look at ERAP2d.py, a Python module for easy numerical simulations of ERAPs.