Extremal Optimization for Graph Partitioning

Details Extremal Optimization for Graph Partitioning Extremal Optimization for Graph Partitioning

2001-04-12

arxiv.org/abs/cond-mat/0104214v1

Phys. Rev. E, 64 (2001) 026114

Physics

Condensed Matter

Statistical Mechanics

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

Scientific paper

10.1103/PhysRevE.64.026114

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.

Affiliated with

Also associated with

No associations

Rating

Extremal Optimization for Graph Partitioning 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 for Graph Partitioning, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal Optimization for Graph Partitioning will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-441449