Document 
Eur. Phys. J. B 46, 501-505 (2005)
DOI: 10.1140/epjb/e2005-00280-6
Extremal optimization for Sherrington-Kirkpatrick spin glasses
S. BoettcherPhysics Department, Emory University, Atlanta, Georgia 30322, USA
sboettc@emory.edu
(Received 6 January 2005 / Received in final form 3 May 2005 / Published online 7 September 2005)
Abstract
Extremal Optimization (EO), a new local search heuristic, is used
to approximate ground states of the mean-field spin glass model
introduced by Sherrington and Kirkpatrick. The implementation
extends the applicability of EO to systems with highly connected
variables. Approximate ground states of sufficient accuracy and
with statistical significance are obtained for systems with more
than N=1000 variables using 
bonds. The data reproduces
the well-known Parisi solution for the average ground state energy
of the model to about 0.01%, providing a high degree of
confidence in the heuristic. The results support to less than 1%
accuracy rational values of
for the finite-size
correction exponent, and of 
for the fluctuation
exponent of the ground state energies, neither one of which has
been obtained analytically yet. The probability density function
for ground state energies is highly skewed and identical within
numerical error to the one found for Gaussian bonds. But
comparison with infinite-range models of finite connectivity shows
that the skewness is connectivity-dependent.
75.10.Nr - Spin-glass and other random models.
02.60.Pn - Numerical optimization.
05.50.+q - Lattice theory and statistics (Ising, Potts, etc.).
© EDP Sciences, Società Italiana di Fisica, Springer-Verlag 2005