Extremal optimization for graph partitioning - art. no. 026114

Extremal optimization is a new general-purpose method for approximating sol utions to hard optimization problems. We study the method in detail by way of the computationally hard (NP-hard) graph partitioning problem. We discus s the scaling behavior of extremal optimization, focusing on the convergenc e of the average run as a function of run time and system size. The method has a single free parameter, which we determine numerically and justify usi ng a simple argument. On random graphs, our numerical results demonstrate t hat extremal optimization maintains consistent accuracy for increasing syst em sizes, with an approximation error decreasing over run time roughly as a power law t(-0.4). On geometrically structured graphs, the scaling of resu lts from the average run suggests that these are far from optimal with larg e fluctuations between individual trials. But when only the best runs are c onsidered, results consistent with theoretical arguments are recovered.