Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm
Liers, Frauke and Palassini, Matteo and Hartmann, Alexander K. and Jünger, Michael
(2003)
Ground state of the Bethe lattice spin glass and running time of an exact optimization algorithm.
Published in:
Physical Review B Vol. 68 (9).
094406.
Abstract
We study the Ising spin glass on random graphs with fixed connectivity z and with a Gaussian distribution of the couplings, with mean mu and unit variance. We compute exact ground states by branch-and-cut with z=4,6 and system sizes up to 1280 spins, for different values of mu . We locate the spin-glass/ferromagnet phase transition 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.
Download: |
Download (543kB) | Preview |
---|---|
Download: |
Download (360kB) | Preview |
Editorial actions: | ![]() |
ZAIK Number: | zaik2003-446 |
---|---|
Depositing User: | Frauke Liers |
Date Deposited: | 19 Apr 2008 00:00 |
Last Modified: | 06 Feb 2012 16:10 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/446 |