Numéro
J. Physique Lett.
Volume 46, Numéro 17, septembre 1985
Page(s) 771 - 778
DOI https://doi.org/10.1051/jphyslet:019850046017077100
J. Physique Lett. 46, 771-778 (1985)
DOI: 10.1051/jphyslet:019850046017077100

Replicas and optimization

M. Mézard et G. Parisi

Dipartimento di Fisica, Università di Roma I, Piazzale A. Moro 2, I-00185 Roma, Italy


Abstract
We use the replica method to study the (bipartite) weighted matching problem with independent random distances between the points. We propose a replica symmetric solution which fits the numerical values of the minimal length and the distribution of lengths of the occupied links in the optimal configuration.


Résumé
Nous utilisons la méthode des répliques pour étudier le problème du matching (bipartite) avec des distances aléatoires indépendantes entre les points. Nous proposons une solution, symétrique dans les répliques, qui est en accord avec les valeurs numériques de la longueur minimale et la distribution des longueurs des liens occupés dans la configuration optimale.

PACS
0520 - Statistical mechanics.
0540 - Fluctuation phenomena, random processes, and Brownian motion.

Key words
random processes -- statistical mechanics -- optimization -- replica method -- weighted matching problem -- random distances -- replica symmetric solution -- optimal configuration