Extremal Optimization of Graph Partitioning at the Percolation Threshold

Details Extremal Optimization of Graph Partitioning at the Percolation Threshold Extremal Optimization of Graph Partitioning at the Percolation Threshold

1999-01-29

arxiv.org/abs/cond-mat/9901353v2

Journal of Physics A: Math. Gen., 32 (1999) 5201

Physics

Condensed Matter

Statistical Mechanics

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

Scientific paper

10.1088/0305-4470/32/28/302

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.

Affiliated with

Also associated with

No associations

Rating

Extremal Optimization of Graph Partitioning at the Percolation Threshold does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Extremal Optimization of Graph Partitioning at the Percolation Threshold, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal Optimization of Graph Partitioning at the Percolation Threshold will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-92753