Near optimal configurations in mean field disordered systems

Andrea Pagnani 1, Giorgio Parisi 2, Mathieu Ratieville 1, 2

Physical Review E: Statistical, Nonlinear, and Soft Matter Physics 68 (2003) 046706

We present a general technique to compute how the energy of a configuration varies as a function of its overlap with the ground state in the case of optimization problems. Our approach is based on a generalization of the cavity method to a system interacting with its ground state. With this technique we study the random matching problem as well as the mean field diluted spin glass. As a byproduct of this approach we calculate the de Almeida-Thouless transition line of the spin glass on a fixed connectivity random graph.

  • 1. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud
  • 2. Dipartimento di Fisica, SMC, INFM, and INFN,
    Università degli studi di Roma I - La Sapienza