Mean field and corrections for the Euclidean Minimum Matching problem

Abstract

Consider the length $L_{MM}^E$ of the minimum matching of N points in d-dimensional Euclidean space. Using numerical simulations and the finite size scaling law $<L_{MM}^E>={\beta }_{MM}^E(d)N^{1-1/d}(1+A/N+...)$, we obtain precise estimates of ${\beta }_{MM}^E(d)$ for $2\le d\le 10$. We then consider the approximation where distance correlations are neglected. This model is solvable and gives at $d\ge 2$ an excellent ``random link'' approximation to ${\beta }_{MM}^E(d)$. Incorporation of three-link correlations further improves the accuracy, leading to a relative error of 0.4% at d=2 and 3. Finally, the large d behavior of this expansion in link correlations is discussed.

source and one figure. Submitted to PRL

Cited by in corpus (4)

• Quadratic stochastic Euclidean bipartite matching problem
• Analytical calculation of neighborhood order probabilities for high dimensional Poissonic processes and mean field models
• An efficient algorithm to generate large random uncorrelated Euclidean distances: the random link model
• The statistical mechanics of multi-index matching problems with site disorder