Mean field and corrections for the Euclidean minimum matching problem

被引:7
作者
deMonvel, JHB
Martin, OC
机构
[1] Division de Physique Théorique, Institut de Physique Nucléaire, Université Paris-Sud, Orsay
关键词
D O I
10.1103/PhysRevLett.79.167
中图分类号
O4 [物理学];
学科分类号
0702 ;
摘要
The minimum matching of N random points in d-dimensional Euclidean space is a tractable model of frustration with disorder. We use numerical simulations to obtain precise estimates of the ground-state energy for 2 less than or equal to d less than or equal to 10. We then consider the approximation where distance correlations are neglected. This model's solution leads to an excellent ''random link'' approximation at d greater than or equal to 2. Incorporating three-link correlations improves the accuracy, leading to a relative error of 0.4% at d = 2 and 3. Finally, we argue that the Euclidean model's lid series is beyond all orders of a link correlation expansion.
引用
收藏
页码:167 / 170
页数:4
相关论文
共 21 条
[1]   AN ANALYSIS OF ALTERNATIVE STRATEGIES FOR IMPLEMENTING MATCHING ALGORITHMS [J].
BALL, MO ;
DERIGS, U .
NETWORKS, 1983, 13 (04) :517-549
[2]   EXTENSIVE NUMERICAL SIMULATIONS OF WEIGHTED MATCHINGS - TOTAL LENGTH AND DISTRIBUTION OF LINKS IN THE OPTIMAL SOLUTION [J].
BRUNETTI, R ;
KRAUTH, W ;
MEZARD, M ;
PARISI, G .
EUROPHYSICS LETTERS, 1991, 14 (04) :295-301
[3]  
Cerf NJ, 1997, J PHYS I, V7, P117, DOI 10.1051/jp1:1997129
[4]  
DEMONVEL JB, 1996, THESIS I PHYSIQUE NU
[5]  
DOMINICIS CD, 1991, J PHYS A, V24, pL301
[6]  
DOMINICIS CD, 1987, EUROPHYS LETT, V3, P87
[7]   SCALING IN SPIN-GLASSES [J].
FISHER, DS ;
SOMPOLINSKY, H .
PHYSICAL REVIEW LETTERS, 1985, 54 (10) :1063-1066
[8]   EQUILIBRIUM BEHAVIOR OF THE SPIN-GLASS ORDERED PHASE [J].
FISHER, DS ;
HUSE, DA .
PHYSICAL REVIEW B, 1988, 38 (01) :386-411
[9]   THE 1-D EXPANSION OF THE EDEN MODEL [J].
FRIEDBERG, R .
PHYSICS LETTERS A, 1985, 112 (3-4) :129-132
[10]   LOW-TEMPERATURE PHASE OF THE ISING SPIN-GLASS ON A HYPERCUBIC LATTICE [J].
GEORGES, A ;
MEZARD, M ;
YEDIDIA, JS .
PHYSICAL REVIEW LETTERS, 1990, 64 (24) :2937-2940