Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Extremal optimization for graph partitioning.

S Boettcher1, A G Percus

  • 1Physics Department, Emory University, Atlanta, Georgia 30322, USA. sboettc@emory.edu

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 11, 2001
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Urinary retention: benefit of gradual bladder decompression - myth or truth? A randomized controlled trial.

Urologia internationalis·2013
Same author

Renormalization group for critical phenomena in complex networks.

Frontiers in physiology·2011
Same author

Quantum transport through hierarchical structures.

Physical review. E, Statistical, nonlinear, and soft matter physics·2011
Same author

Fixed-point properties of the Ising ferromagnet on the Hanoi networks.

Physical review. E, Statistical, nonlinear, and soft matter physics·2011
Same author

Decomposition of the telomere-targeting agent BRACO19 in physiological media results in products with decreased inhibitory potential.

International journal of pharmaceutics·2008
Same author

Thermal inactivation of foot-and-mouth disease virus in milk using high-temperature, short-time pasteurization.

Journal of dairy science·2007
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

Extremal optimization, a method for hard optimization problems, shows consistent accuracy on random graphs. Its approximation error decreases over time, demonstrating scalability for complex computational challenges like graph partitioning.

Area of Science:

  • Computational complexity
  • Optimization algorithms

Background:

  • Extremal optimization is a novel approach for tackling computationally difficult optimization problems.
  • The graph partitioning problem, known for its NP-hard nature, serves as a benchmark for evaluating optimization methods.

Purpose of the Study:

  • To analyze the scaling behavior and convergence properties of extremal optimization.
  • To determine and justify the single free parameter of the extremal optimization method.
  • To assess the performance of extremal optimization on both random and geometrically structured graphs.

Main Methods:

  • Investigated extremal optimization applied to the graph partitioning problem.
  • Analyzed the convergence of average runs concerning run time and system size.
  • Numerically determined and theoretically justified the method's free parameter.

Related Experiment Videos

Main Results:

  • Extremal optimization exhibited consistent accuracy across increasing system sizes on random graphs.
  • Approximation error decreased over run time following a power law (t^-0.4).
  • On structured graphs, average runs showed significant variability, but best runs aligned with theoretical predictions.

Conclusions:

  • Extremal optimization demonstrates effective scaling and consistent performance on random graph partitioning.
  • The method's parameter is validated, and its behavior on structured graphs highlights the importance of considering individual trial performance.