Replica bounds for optimization problems and diluted spin systems

Abstract

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 method provides an improvable scheme to obtain lower bounds of the free-energy at all temperatures and of the ground state energy. In the case of K-SAT the replica method thus gives upper bounds of the satisfiability threshold.

18 pages, 1 figure

Cited by in corpus (15)

• Extremal Cuts of Sparse Random Graphs
• Information-theoretic thresholds from the cavity method
• Combinatorial approach to the interpolation method and scaling limits in sparse random graphs
• Catching the k-NAESAT Threshold
• The Phase Diagram of 1-in-3 Satisfiability Problem
• The Stable Marriage Problem: an Interdisciplinary Review from the Physicist's Perspective
• Structure of finite-RSB asymptotic Gibbs measures in the diluted spin glass models
• The marginally stable Bethe lattice spin glass revisited
• Structure of 1-RSB asymptotic Gibbs measures in the diluted p-spin models
• The random 2-SAT partition function
• Replica Bounds by Combinatorial Interpolation for Diluted Spin Systems
• The full replica symmetry breaking in the Ising spin glass on random regular graph
• Exact and Approximate Solutions for the Dilute Ising Model
• Concentration of multi-overlaps for random ferromagnetic spin models
• On the probabilistic approach to the random satisfiability problem