Back to Search
Start Over
Random multi-overlap structures for optimization problems.
- Source :
-
Journal of Mathematical Physics . Nov2005, Vol. 46 Issue 11, p113302. 8p. - Publication Year :
- 2005
-
Abstract
- 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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00222488
- Volume :
- 46
- Issue :
- 11
- Database :
- Academic Search Index
- Journal :
- Journal of Mathematical Physics
- Publication Type :
- Academic Journal
- Accession number :
- 19071042
- Full Text :
- https://doi.org/10.1063/1.2121267