Replica Bounds for Optimization Problems and Diluted Spin Systems
Replica Bounds for Optimization Problems and Diluted Spin Systems
复制标题
优化问题和稀释自旋系统的副本界限
DOI：
--
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
M. Leone
中科院分区：
文献类型：
--
作者：
S. Franz;M. Leone
在本文中，我们推广到稀释自旋模型和随机组合优化问题的情况下，最近推出的Guerra（cond-mat/0205123），以证明副本方法产生的无序系统的变分界限的技术。我们分析了一个家庭的模型，其中包括Viana-Bray模型，稀释的p-自旋模型或随机XOR-SAT问题，和随机K-SAT问题，表明副本/腔的方法，在不同的近似水平，提供系统的计划，以获得在所有温度下的自由能和基态能量的下限。在K-SAT和XOR-SAT的情况下，它因此给出了可满足性阈值的上界。我们的分析强调了与空腔方法的深层联系，而这种联系在长距离情况下并不明显。
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.