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

Criticality and parallelism in combinatorial optimization

W G Macready1, A G Siapas, S A Kauffman

  • 1Santa Fe Institute, NM 87501, USA.

Science (New York, N.Y.)
|January 5, 1996
PubMed
Summary

Parallelizing local search for optimization problems improves performance up to a point, after which it degrades significantly. This study demonstrates this transition in spin-glass models and the traveling salesman problem.

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

Extrinsic and intrinsic effects setting viscosity in complex fluids and life processes: the role of fundamental physical constants.

The European physical journal. E, Soft matter·2025
Same author

Mixed anhydrides at the intersection between peptide and RNA autocatalytic sets: evolution of biological coding.

Interface focus·2023
Same author

Robustness analysis of a Boolean model of gene regulatory network with memory.

Journal of computational biology : a journal of computational molecular cell biology·2011
Same author

Cell-cell interaction and diversity of emergent behaviours.

IET systems biology·2011
Same author

Phase transition in a class of nonlinear random networks.

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

On the dynamics of random Boolean networks subject to noise: attractors, ergodic sets and cell types.

Journal of theoretical biology·2010

Area of Science:

  • Computational complexity
  • Optimization algorithms
  • Statistical physics

Background:

  • Local search methods are effective for large-scale combinatorial optimization.
  • Parallelization of these methods initially boosts performance.
  • A critical point exists where performance degrades drastically.

Purpose of the Study:

  • To investigate the performance degradation of parallelized local search.
  • To identify the transition point in optimization performance.
  • To analyze the underlying mechanisms of this phenomenon.

Main Methods:

  • Demonstration on generalized spin-glass models.
  • Application to the traveling salesman problem.
  • Utilizing finite-size scaling analysis.
  • Employing mean-field approximation for analytical insights.

Main Results:

  • Confirmed an abrupt performance degradation in parallelized local search.
  • Characterized size-dependent effects near the transition point.
  • Provided analytical understanding through mean-field theory.

Conclusions:

  • Parallelization of local search has inherent limitations.
  • Understanding this transition is crucial for effective algorithm design.
  • The findings offer insights into the scalability of optimization techniques.

Related Experiment Videos