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.


Actions:
Download: [img] Postscript - Preprinted Version
Download (530Kb) | Preview
Download: [img] PDF - Preprinted Version
Download (352Kb) | Preview
Export as:
Editorial actions: View Item View Item (Login required)
Deposit Information:
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