Home Publications Research Grants Inventions & Patents Awards Additional Research Activities Faculties & Institutions Research Areas

Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm

Liers F, Palassini M, Hartmann AK, Jünger M (2003)

---

Publication Status: Published

Publication Type: Journal article, Original article

Publication year: 2003

Journal

Publisher: American Physical Society

Book Volume: 68

Pages Range: 944061-944069

Article Number: 094406

Journal Issue: 9

URI: https://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=0242267921&origin=inward

Abstract

We study the Ising spin glass on random graphs with fixed connectivity z and with a Gaussian distribution of the couplings, with mean μ and unit variance. We compute exact ground states by using a sophisticated branch-and-cut method for z = 4,6 and system sizes up to 1280 spins, for different values of μ. We locate the spin-glass/ferromagnet phase transition at μ = 0.77±0.02 (z = 4) and μ = 0.56±0.02 (z = 6). We also compute the energy and magnetization in the Bethe-Peierls approximation with a stochastic method, and estimate the magnitude of replica symmetry breaking corrections. Near the phase transition, we observe a sharp change of the median running time of our implementation of the algorithm, consistent with a change from a polynomial dependence on the system size, deep in the ferromagnetic phase, to slower than polynomial in the spin-glass phase.

Authors with CRIS profile

Involved external institutions

How to cite

APA:

Liers, F., Palassini, M., Hartmann, A.K., & Jünger, M. (2003). Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm. Physical Review B, 68(9), 944061-944069.

MLA:

Liers, Frauke, et al. "Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm." Physical Review B 68.9 (2003): 944061-944069.

BibTeX: Download