Comparing mean field and Euclidean matching problems

Combinatorial optimization is a fertile testing ground for statistical phys ics methods developed in the context of disordered systems, allowing one to confront theoretical mean field predictions with actual properties of fini te dimensional systems. Our focus here is on minimum matching problems, bec ause they are computationally tractable while both frustrated and disordere d. We first study a mean field model taking the link lengths between points to be independent random variables. For this model we find perfect agreeme nt with the results of a replica calculation: and give a conjecture. Then w e study the case where the points to be matched are placed at random in a d -dimensional Euclidean space. Using the mean field model as an approximatio n to the Euclidean case, we show numerically that the mean field prediction s are very accurate even at low dimension, and that the error due to the ap proximation is O(1/d(2)). Furthermore, it is possible to improve upon this approximation by including the effects of Euclidean correlations among k li nk lengths. Using k = 3 (3-link correlations such as the triangle inequalit y), the resulting errors in the energy density are already less than 0.5% a t d greater than or equal to 2. However, we argue that the dimensional depe ndence of the Euclidean model's energy density is non-perturbative, i.e., i t is beyond all orders in k of the expansion in k-link correlations.