Jamming model for the extremal optimization heuristic

Extremal optimization, a recently introduced meta-heuristic for hard optimization problems, is analysed 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 phenomenology found in all earlier studies of extremal optimization, and our analytical results for the model reproduce many of these features. PACS numbers: 02.60.Pn, 05.40.−a, 64.60.Cn, 75.10.Nr (Some figures in this article are in colour only in the electronic version) 1