Extremal Optimization for Graph Partitioning

Abstract

Extremal optimization is a new general-purpose method for approximating solutions to hard optimization problems. We study the method in detail by way of the NP-hard graph partitioning problem. We discuss the scaling behavior of extremal optimization, focusing on the convergence of the average run as a function of runtime and system size. The method has a single free parameter, which we determine numerically and justify using a simple argument. Our numerical results demonstrate that on random graphs, extremal optimization maintains consistent accuracy for increasing system sizes, with an approximation error decreasing over runtime roughly as a power law t^(-0.4). On geometrically structured graphs, the scaling of results from the average run suggests that these are far from optimal, with large fluctuations between individual trials. But when only the best runs are considered, results consistent with theoretical arguments are recovered.

34 pages, RevTex4, 1 table and 20 ps-figures included, related papers available at http://www.physics.emory.edu/faculty/boettcher/

References in corpus (2)

• Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
• Optimization by thermal cycling

Cited by in corpus (25)

• Comparing community structure identification
• Community detection in complex networks using Extremal Optimization
• Random Geometric Graphs
• Phase Transitions in the Coloring of Random Graphs
• Improved community structure detection using a modified fine tuning strategy
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• 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
• Probing tails of energy distributions using importance-sampling in the disorder with a guiding function
• Simulations of Ground State Fluctuations in Mean-Field Ising Spin Glasses
• Belief propagation for graph partitioning
• Optimizing at the Ergodic Edge
• On Multiobjective Evolution Model
• Graph Partitioning Induced Phase Transitions
• Extremal optimization for sensor report pre-processing
• Graph Neural Networks for Maximum Constraint Satisfaction
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• The network source location problem: ground state energy, entropy and effects of freezing
• Optimization via Quantum Preconditioning
• Experimental performance of graph neural networks on random instances of max-cut
• Cluster structure of optimal solutions in bipartitioning of small worlds
• Bipartitioning of directed and mixed random graphs
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers