https://doi.org/10.1140/epjb/e2005-00280-6
Extremal optimization for Sherrington-Kirkpatrick spin glasses
Physics Department, Emory University, Atlanta, Georgia
30322, USA
Corresponding author: a sboettc@emory.edu
Received:
6
January
2005
Revised:
3
May
2005
Published online:
7
September
2005
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.
PACS: 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
