ISSN:
1434-6036
Keywords:
PACS. 75.10.Nr Spin-glass and other random models – 02.60.Pn Numerical optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Physics
Notes:
Abstract: 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 p k = 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00011144
Permalink
