Physics – Condensed Matter – Statistical Mechanics
Scientific paper
2001-04-23
Theoretical Computer Science 265 (1-2) (2001) 3-67
Physics
Condensed Matter
Statistical Mechanics
Review article, 80 pages, uses elsart.cls
Scientific paper
Recently, it has been recognized that phase transitions play an important role in the probabilistic analysis of combinatorial optimization problems. However, there are in fact many other relations that lead to close ties between computer science and statistical physics. This review aims at presenting the tools and concepts designed by physicists to deal with optimization or decision problems in an accessible language for computer scientists and mathematicians, with no prerequisites in physics. We first introduce some elementary methods of statistical mechanics and then progressively cover the tools appropriate for disordered systems. In each case, we apply these methods to study the phase transitions or the statistical properties of the optimal solutions in various combinatorial problems. We cover in detail the Random Graph, the Satisfiability, and the Traveling Salesman problems. References to the physics literature on optimization are provided. We also give our perspective regarding the interdisciplinary contribution of physics to computer science.
Martin Olivier C.
Monasson Remi
Zecchina Riccardo
No associations
LandOfFree
Statistical mechanics methods and phase transitions in optimization problems 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 Statistical mechanics methods and phase transitions in optimization problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Statistical mechanics methods and phase transitions in optimization problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-449177