Search

The average ground state energies for spin glasses on Bethe lattices of connectivities r = 3,...,15 are studied numerically for a Gaussian bond distribution. The Extremal Optimization heuristic is employed which provides high-quality approximations to ground states. The energies obtained from extrapolation to the thermodynamic limit smoothly approach the ground-state energy of the Sherrington-Kirkpatrick model for r ↦ ∞. Consistently for all values of r in this study, finite-size corrections are found to decay approximately with ~N-4/5. The possibility of ~N-2/3 corrections, found previously for Bethe lattices with a bimodal ± J bond distribution and also for the Sherrington-Kirkpatrick model, are constrained to the additional assumption of very specific higher-order terms. Instance-to-instance fluctuations in the ground state energy appear to be asymmetric up to the limit of the accuracy of our heuristic. The data analysis provides insights into the origin of trivial fluctuations when using continuous bonds and/or sparse networks. [ABSTRACT FROM AUTHOR]

The Karmarkar-Karp differencing algorithm is the best known polynomial time heuristic for the number partitioning problem, fundamental in both theoretical computer science and statistical physics. We analyze the performance of the differencing algorithm on random instances by mapping it to a nonlinear rate equation. Our analysis reveals strong finite size effects that explain why the precise asymptotics of the differencing solution is hard to establish by simulations. The asymptotic series emerging from the rate equation satisfies all known bounds on the Karmarkar-Karp algorithm and projects a scaling n − c ln n , where c = 1/(2 ln 2) = 0.7213 .... Our calculations reveal subtle relations between the algorithm and Fibonacci-like sequences, and we establish an explicit identity to that effect. [ABSTRACT FROM AUTHOR]

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 ±J 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 ω=2/3 for the finite-size correction exponent, and of ρ=3/4 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. [ABSTRACT FROM AUTHOR]

Using a non-thermal local search, called Extremal Optimization (EO), in conjunction with a recently developed scheme for classifying the valley structure of complex systems, we analyze a short-range spin glass. In comparison with earlier studies using a thermal algorithm with detailed balance, we determine which features of the landscape are algorithm dependent and which are inherently geometrical. Apparently a characteristic for any local search in complex energy landscapes, the time series of successive energy records found by EO is also characterized approximately by a Poisson statistic with logarithmic time arguments. Differences in the results provide additional insights into the performance of EO. In contrast with a thermal search, the extremal search visits dramatically higher energies while returning to more widely separated low-energy configurations. Two important properties of the energy landscape are independent of either algorithm: first, to find lower energy records, progressively higher energy barriers need to be overcome. Second, the Hamming distance between two consecutive low-energy records is linearly related to the height of the intervening barrier. [ABSTRACT FROM AUTHOR]

Examines the stiffness exponents in the glass phase for lattice spin glasses. Methods used to determine stiffness exponents; Description of the reduction rules for low-connected spins; Analysis of the ground state energy of the reduced graph with external optimization heuristic.

A reduction procedure to obtain ground states of spin glasses on sparse graphs is developed and tested on the hierarchical lattice associated with the Migdal-Kadanoff approximation for low-dimensional lattices. While more generally applicable, these rules here lead to a complete reduction of the lattice. The stiffness exponent governing the scaling of the defect energy ΔE with system size L, σ(ΔE) ~Ly, is obtained as y3 = 0.25546(3) by reducing the equivalent of lattices up to L = 2100 in d = 3, and as y4 = 0.76382(4) for up to L = 235 in d = 4. The reduction rules allow the exact determination of the ground state energy, entropy, and also provide an approximation to the overlap distribution. With these methods, some well-know and some new features of diluted hierarchical lattices are calculated. [ABSTRACT FROM AUTHOR]

Discusses the numerical approximation of the average ground state energy and entropy for spin glasses on Bethe lattices of connectivities. Use of Extremal Optimization heuristic in the approximation process; Investigation on disordered spin systems on random graphs; Information on Bethe lattices.