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

Beitrag in einer Fachzeitschrift
(Originalarbeit)


Details zur Publikation

Autorinnen und Autoren: Liers F, Palassini M, Hartmann AK, Jünger M
Zeitschrift: Physical Review B
Verlag: American Physical Society
Jahr der Veröffentlichung: 2003
Band: 68
Heftnummer: 9
Seitenbereich: 944061-944069
ISSN: 0163-1829


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.



FAU-Autorinnen und Autoren / FAU-Herausgeberinnen und Herausgeber

Liers-Bergmann, Frauke Prof. Dr.
Professur für Angewandte Mathematik (Ganzzahlige und robuste Optimierung)


Einrichtungen weiterer Autorinnen und Autoren

Carl von Ossietzky Universität Oldenburg
Universitat de Barcelona (UB) / University of Barcelona
Universität Köln


Zitierweisen

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: 

Zuletzt aktualisiert 2018-10-08 um 06:11