Phys. Rev. E 70, 036107 (2004) [11 pages]

Minimizing energy below the glass thresholds

Abstract

References

Citing Articles (4)

Download: PDF (143 kB) Buy this article Export: BibTeX or EndNote (RIS)

Demian Battaglia^1,*, Michal Kolář^1,†, and Riccardo Zecchina^2,‡
¹SISSA, Via Beirut 9, I-34100 Trieste, Italy
²ICTP, Strada Costiera 11, I-34100 Trieste, Italy

Received 26 February 2004; published 15 September 2004

Focusing on the optimization version of the random K-satisfiability problem, the MAX-K-SAT problem, we study the performance of the finite energy version of the survey propagation algorithm. We show that a simple (linear time) backtrack decimation strategy is sufficient to reach configurations well below the lower bound for the dynamic threshold energy and very close to the analytic prediction for the optimal ground states. A comparative numerical study on one of the most efficient local search procedures is also given.

URL:

http://link.aps.org/doi/10.1103/PhysRevE.70.036107

DOI:

10.1103/PhysRevE.70.036107

PACS:

02.50.−r, 75.10.Nr, 02.60.Pn, 05.20.−y

^*Electronic address: battagli@sissa.it

^†Electronic address: kolarmi@sissa.it

^‡Electronic address: zecchina@ctp.trieste.it

About | Terms and Conditions | Subscriptions | Search | Help

Use of the American Physical Society websites and journals implies that the user has read and agrees to our Terms and Conditions and any applicable Subscription Agreement. Physical Review®, Physical Review Letters®, Reviews of Modern Physics®, and Physical Review Special Topics® are trademarks of the American Physical Society.

Citation Search:

Phys. Rev. E 70, 036107 (2004) [11 pages]

Minimizing energy below the glass thresholds