S. Boettcher, M. Grigni
Published 2001-10-09, updated 2001-12-12Version 2
Extremal Optimization, a recently introduced meta-heuristic for hard optimization problems, is analyzed on a simple model of jamming. The model is motivated first by the problem of finding lowest energy configurations for a disordered spin system on a fixed-valence graph. The numerical results for the spin system exhibit the same phenomena found in all earlier studies of extremal optimization, and our analytical results for the model reproduce many of these features.
Comments: 9 pages, RevTex4, 7 ps-figures included, as to appear in J. Phys. A, related papers available at http://www.physics.emory.edu/faculty/boettcher/
Journal: Journal of Physics A: Math. Gen., 35 (2002) 1109
Statistical Physics of Hard Optimization Problems
On Spin Systems with Quenched Randomness: Classical and Quantum
First- and Second-Order Transitions between Quantum and Classical Regimes for the Escape Rate of a Spin System
