2000/10/31 by Stefan Boettcher, S. Boettcher, Allon G. Percus +1 · 4 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Complex Network Analysis Techniques #Computer science #Criticality #Discrete optimization #Extremal optimization #Heuristic #Mathematical optimization #Mathematics #Meta-optimization #Optimization problem #Physics #Quantum mechanics #Spin glass #Statistical physics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.stat-mech #cs.NE #math.OC
paper · pdf · doi:10.1103/physrevlett.86.5211
published as Phys. Rev. Lett, 86 (2001) 5211 · 4 pages, RevTex4, 1 table and 3 ps-figures included, as to appear in PRL, related papers available at http://www.physics.emory.edu/faculty/boettcher/
arxiv created 2001/04/08 · openalex publication_date 2001/06/04 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.