Replica bounds for optimization problems and diluted spin systems

Details Replica bounds for optimization problems and diluted spin systems Replica bounds for optimization problems and diluted spin systems

2002-08-14

arxiv.org/abs/cond-mat/0208280v1

J. Stat. Phys. 111 (2003) 535-564

Physics

Condensed Matter

Disordered Systems and Neural Networks

18 pages, 1 figure

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Replica bounds for optimization problems and diluted spin systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Replica bounds for optimization problems and diluted spin systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Replica bounds for optimization problems and diluted spin systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-290917