Random multi-overlap structures for optimization problems
Luca De Sanctis · Journal of Mathematical Physics · 2005
We extend to the K-SAT and p-XOR-SAT optimization problems the results recently achieved, by introducing the concept of random multi-overlap structure, for the Viana-Bray model of diluted mean field spin glass. More precisely we can prove a generalized bound and an extended variational principle for the free energy per site in the thermodynamic limit. Moreover a trial function implementing ultrametric breaking of replica symmetry is exhibited. The ultrametric structure exhibits the same factorization property as the optimal structures for the Viana-Bray model and the Sherrington-Kirkpatrick nondiluted model.