Eur. Phys. J. B 6, 383-393 (1998)
https://doi.org/10.1007/s100510050565

Comparing mean field and Euclidean matching problems

¹ Division de Physique Théorique, Institut de Physique Nucléaire, Université Paris-Sud, 91406 Orsay Cedex, France
² Forschungszentrum BiBos, Fakultät für Physik, Universität Bielefeld, 33615 Bielefeld, Germany

Corresponding authors: ^a houdayer@ipno.in2p3.fr - ^b jacques.boutet.de.monvel@ood.ki.se

Received: 1 December 1997
Revised: 6 May 1998
Accepted: 30 June 1998
Published online: 15 December 1998

Abstract

Combinatorial optimization is a fertile testing ground for statistical physics methods developed in the context of disordered systems, allowing one to confront theoretical mean field predictions with actual properties of finite dimensional systems. Our focus here is on minimum matching problems, because they are computationally tractable while both frustrated and disordered. We first study a mean field model taking the link lengths between points to be independent random variables. For this model we find perfect agreement with the results of a replica calculation, and give a conjecture. Then we 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 approximation to the Euclidean case, we show numerically that the mean field predictions are very accurate even at low dimension, and that the error due to the approximation is . Furthermore, it is possible to improve upon this approximation by including the effects of Euclidean correlations among k link lengths. Using k=3 (3-link correlations such as the triangle inequality), the resulting errors in the energy density are already less than at . However, we argue that the dimensional dependence of the Euclidean model's energy density is non-perturbative, i.e., it is beyond all orders in k of the expansion in k-link correlations.