Replica Bounds for Optimization Problems and Diluted Spin Systems
Abstrak
In this paper we generalize to the case of diluted spin models and random combinatorial optimization problems a technique recently introduced by Guerra (cond-mat/0205123) to prove that the replica method generates variational bounds for disordered systems. We analyze a family of models that includes the Viana–Bray model, the diluted p-spin model or random XOR-SAT problem, and the random K-SAT problem, showing that the replica/cavity method, at the various levels of approximation, provides systematic schemes to obtain lower bounds of the free-energy at all temperatures and of the ground state energy. In the case of K-SAT and XOR-SAT it thus gives upper bounds of the satisfiability threshold. Our analysis underlines deep connections with the cavity method which are not evident in the long range case.
Topik & Kata Kunci
Penulis (2)
S. Franz
M. Leone
Akses Cepat
- Tahun Terbit
- 2002
- Bahasa
- en
- Total Sitasi
- 192×
- Sumber Database
- Semantic Scholar
- DOI
- 10.1023/A:1022885828956
- Akses
- Open Access ✓