Neighborhood preferences in random matching problems
Dipartimento di Fisica, INFM and INFN, Università di Roma 1 "La Sapienza" , P.le A. Moro, 2, 00185 Roma, Italy
Published online: 15 July 2001
We consider a class of random matching problems where the distance between two points has a probability law which, for a small distance l, goes like lr. In the framework of the cavity method, in the limit of an infinite number of points, we derive equations for pk, the probability for some given point to be matched to its kth nearest neighbor in the optimal configuration. These equations are solved in two limiting cases: r=0 -where we recover pk=1/2k, as numerically conjectured by Houdayer et al. and recently rigorously proved by Aldous - and r → +∞. For 0<r<+∞, we are not able to solve the equations analytically, but we compute the leading behavior of pk for large k.
PACS: 75.10.Nr – Spin-glass and other random models / 02.60.Pn – Numerical optimization
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag, 2001