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

Statistical mechanics of combinatorial optimization problems with site disorder.

David S Dean1, David Lancaster, Satya N Majumdar

  • 1Laboratoire de Physique Théorique, UMR CNRS 5152, IRSAMC, Université Paul Sabatier, 118 route de Narbonne, 31062 Toulouse Cedex 04, France.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 4, 2005
PubMed
Summary

This study introduces a new statistical mechanics method for analyzing problems with quenched disorder, like the traveling salesman problem. The approach, validated by simulations, offers an alternative to replica methods for complex systems.

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

Proxitaxis: An adaptive search strategy based on proximity and stochastic resetting.

Physical review. E·2026
Same author

Dynamically emergent correlations in Brownian particles subject to simultaneous non-Poissonian resetting protocols.

Physical review. E·2026
Same author

Target Search Optimization by Threshold Resetting.

Physical review letters·2025
Same author

Enhanced diffusion over a periodic trap by hydrodynamic coupling to an elastic mode.

Communications physics·2025
Same author

Diffusion with stochastic resetting on a lattice.

Physical review. E·2025
Same author

Solving Lyapunov equations for electrically driven ternary electrolytes: Application to long-range van der Waals interactions.

Physical review. E·2025

Area of Science:

  • Statistical mechanics
  • Computational physics
  • Combinatorial optimization

Background:

  • Many complex systems exhibit quenched disorder, affecting their statistical properties.
  • Existing methods like the replica method can be mathematically intensive.
  • The traveling salesman problem (TSP) and descent problem are examples of such systems.

Purpose of the Study:

  • To develop a novel, replica-free formalism for analyzing systems with quenched disorder.
  • To apply this formalism to specific problems like the finite-temperature TSP and one-dimensional descent problems.
  • To provide an alternative computational method for studying quenched disordered systems.

Main Methods:

  • Developed a new formalism for quenched calculations in the large-number-of-points limit.

Related Experiment Videos

  • Utilized the annealed approximation to motivate the primary method.
  • Employed Monte Carlo simulations for validation.
  • Analyzed the finite-temperature traveling salesman problem and one-dimensional descent problems.

    • Main Results:

    • The new formalism successfully predicts results for quenched systems without using the replica method.
    • Predictions align with outcomes from Monte Carlo simulations.
    • The method accurately reproduces an exact result for the 2D maximum TSP and suggests higher-dimensional generalizations.
    • The approach offers a viable alternative for studying systems with quenched disorder.

    Conclusions:

    • The developed formalism provides an effective and computationally tractable method for studying statistical mechanics problems with quenched disorder.
    • This work offers a significant advancement in the analysis of complex systems, particularly in combinatorial optimization.
    • The method's success in reproducing known results and suggesting new ones highlights its potential for broader applications.