Jamming model for the extremal optimization heuristic

doi:10.1088/0305-4470/35/5/301

Jamming model for the extremal optimization heuristic

Stefan Boettcher et al 2002 J. Phys. A: Math. Gen. 35 1109-1123 doi: 10.1088/0305-4470/35/5/301

PDF (205 KB) | Gzipped PS (188 KB) | References | Articles citing this article

Stefan Boettcher¹ and Michelangelo Grigni²
¹ Physics Department, Emory University, Atlanta, GA 30322, USA
² Department of Mathematics and Computer Sciences, Emory University, Atlanta, GA 30322, USA
E-mail: sboettc@emory.edu and mic@mathcs.emory.edu

Abstract. 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

Print publication: Issue 5 (8 February 2002)
Received 9 October 2001, in final form 10 December 2001
Published 25 January 2002

Post to CiteUlike |

Post to Connotea |

Post to Bibsonomy

Jamming model for the extremal optimization heuristic

Find related articles

Article options

Authors & Referees