Random Assignment Problems on 2d Manifolds

We consider the assignment problem between two sets ofNrandom points on a smooth, two-dimensional manifoldof unit area. It is known that the average cost scales asE(N)∼1/2πlnNwith a correction that is at most of order√lnNln lnN. In this paper, we show that,within the linearization approximation of the field-theoretical formulation of the problem,the first-dependent correction is on the constant term, and can be exactly computed fromthe spectrum of the Laplace–Beltrami operator on. We perform the explicit calculation ofthis constant for various families of surfaces, and compare our predictions with extensivenumerics.