Jamming Model for the Extremal Optimization Heuristic

Abstract

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.

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/

References in corpus (16)

• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• Nature of the Spin Glass State
• Glassiness in a model without energy barriers
• Extremal Optimization for Graph Partitioning
• Simplest random K-satisfiability problem
• Slow relaxation in granular compaction
• Exact solutions for diluted spin glasses and optimization problems
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
• Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
• Ground-state behavior of the 3d +/-J random-bond Ising model
• Calculation of ground states of four-dimensional +or- J Ising spin glasses
• Extremal Optimization of Graph Partitioning at the Percolation Threshold
• Multicanonical Methods vs. Molecular Dynamics vs. Monte Carlo: Comparison for Lennard-Jones Glasses
• Glassy Dynamics of Protein Folding

Cited by in corpus (10)

• Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Numerical Results for Ground States of Mean-Field Spin Glasses at low Connectivities
• Continuous extremal optimization for Lennard-Jones Clusters
• Long-Range Anomalous Decay of the Correlation in Jammed Packings
• Comparing extremal and thermal Explorations of Energy Landscapes
• Conjecture on the maximum cut and bisection width in random regular graphs
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Optimizing at the Ergodic Edge
• Approximate analysis of search algorithms with "physical" methods