title: Optimization with extremal dynamics.
abstract: We explore a new general-purpose heuristic for finding high-quality solutions to hard discrete optimization problems. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively updates extremely undesirable variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, efficiently exploring many local optima. We use extremal optimization to elucidate the phase transition in the 3-coloring problem, and we provide independent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.
authors.affiliation: Physics Department, Emory University, Atlanta, Georgia 30322, USA. sboettc@emory.edu
authors.forename: S
authors.initials: S
authors.lastname: Boettcher
authors.forename: A G
authors.initials: AG
authors.lastname: Percus