Extremal optimization of graph partitioning at the percolation threshold

DOI10.1088/0305-4470/32/28/302MaRDI QIDQ4947672zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Boettcher

Publication date 25 April 2000

Published in Journal of Physics A: Mathematical and General (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/cond-mat/9901353

zbMATH Keywords

graph partitionssimulated annealing

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59)

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.

Recommendations

• scientific article; zbMATH DE number 2151246
• Nature's way of optimizing
• scientific article; zbMATH DE number 1941955
• Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
• scientific article; zbMATH DE number 2159026

Cited in

(6)

• Nature's way of optimizing
• The peculiar phase structure of random graph bisection
• scientific article; zbMATH DE number 2151246 (Why is no real title available?)
• Faster Monte Carlo simulations at low temperatures. The waiting time method
• Spines of random constraint satisfaction problems: definition and connection with computational complexity
• Extremal optimization for protein folding simulations on the lattice

This page was built for publication: Extremal optimization of graph partitioning at the percolation threshold

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4947672)