Self-Organizing Dynamics for Combinatorial Optimization

Stefan Boettcher, Department of Physics, Emory University

Applying the dynamics of self-organized criticality for combinatorial problems provides an efficient and quite general optimization heuristic. Frequent recurrences to near-optimal solutions occur without any tuning of parameters. We can solve hard combinatorial problems such as coloring, partitioning, and internet routing. Unpresidented accuracy is obtained measuring low-temperature excitations in spin glasses. Exploring the dynamics of the heuristic reveals deep connections to jamming in granular media.