Extremal Optimization of Graph Partitioning at the Percolation Threshold

Abstract

The benefits of a recently proposed method to approximate hard optimization problems are demonstrated on the graph partitioning problem. The performance of this new method, called Extremal Optimization, is compared to Simulated Annealing in extensive numerical simulations. While generally a complex (NP-hard) problem, the optimization of the graph partitions is particularly difficult for sparse graphs with average connectivities near the percolation threshold. At this threshold, the relative error of Simulated Annealing for large graphs is found to diverge relative to Extremal Optimization at equalized runtime. On the other hand, Extremal Optimization, based on the extremal dynamics of self-organized critical systems, reproduces known results about optimal partitions at this critical point quite well.

7 pages, RevTex, 9 ps-figures included, as to appear in Journal of Physics A

Cited by in corpus (17)

• Random Geometric Graphs
• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• Extremal Optimization for Graph Partitioning
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
• Continuous extremal optimization for Lennard-Jones Clusters
• Comparing extremal and thermal Explorations of Energy Landscapes
• Conjecture on the maximum cut and bisection width in random regular graphs
• Jamming Model for the Extremal Optimization Heuristic
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• d_c=4 is the upper critical dimension for the Bak-Sneppen model
• Optimizing at the Ergodic Edge
• The Peculiar Phase Structure of Random Graph Bisection
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Polynomial Observables in the Graph Partitioning Problem
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers