- Cavity method
The Cavity method is a mathematical method due to M. Mezard,
Giorgio Parisi and M.A. Virasoro in 1985 to compute properties ofground state s in manycondensed matter andoptimization problem s. Initially invented to deal with the Sherrington Kirkpatrick model of spin glasses, it has shown wide applicability. It can be regarded as a generalization of theBethe Peierls iterative method in tree-like graphs to the case of graph with loops that are not too short. The different approximations that can be done with the cavity method are usually named after their equivalent with the different steps of the replica method which is mathematically more subtle and less intuitive than the cavity approach.The cavity method has played and is playing a major role in the solution of
optimization problem s like the K-satisfiability and thegraph coloring in present days. It has yielded not only ground states energy predictions in the average case, but also has inspired algorithmic methods for solving particular instances of anoptimization problem .ee also
References
* "The Bethe lattice spin glass revisited" M. Mezard and G. Parisi, September 14th 2005
* [http://www.interscience.wiley.com Survey Propagation: An Algorithm for Satisfiability] A. Braunstein, M. Mézard, R. Zecchina, Published online 4th March 2005 in Wiley InterScienceExternal links
Wikimedia Foundation. 2010.
