Journal of Mathematical Physics
Feedback | Help | Exit
Search:
   
 
 
 
Previous Article
Universal structures in some mean field spin glasses and an application
We discuss a spin glass reminiscent of the random energy model (REM), which allows, in particular, to recast the Parisi minimization into a more classical Gibbs variational principle, thereby shedding...
Next Article
Susceptibility in subcritical random graphs
We study the evolution of the susceptibility in the subcritical random graph G(n,p) as n tends to infinity. We obtain precise asymptotics of its expectation and variance and show that it obeys a law o...

A rigorous analysis of the cavity equations for the minimum spanning tree

J. Math. Phys. 49, 125206 (2008); doi:10.1063/1.2982805

Published 9 December 2008

You are not logged in to this journal. Log in

Mohsen Bayati,1 Alfredo Braunstein,2 and Riccardo Zecchina2
1Microsoft Research, One Microsoft Way, Redmond, Washington 98052, USA
2Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino, Italy
We analyze a new general representation for the minimum weight Steiner tree problem that translates the topological connectivity constraint into a set of local conditions, which can be analyzed by the so-called cavity equation techniques. For the limit case of the spanning tree, we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum. ©2008 American Institute of Physics
History: Received 27 June 2008; accepted 12 August 2008; published 9 December 2008
Permalink: http://link.aip.org/link/?JMAPAQ/49/125206/1
BUY THIS ARTICLE   (US$24)
Download PDF (257 kB) View Cart

KEYWORDS and PACS

Keywords
PACS

RELATED DATABASES


To view database links for this article,
you need to log in.
To view database links for this article,
you need to log in.

PUBLICATION DATA

ISSN:
0022-2488 (print)   1089-7658 (online)
Publisher:
AIP is a member of CrossRef AIP

REFERENCES (15)
View in Separate Window/Tab
For access to fully linked references, you need to log in. For access to fully linked references, you need to Log in.
  1. R. M. Karp, Complexity of Computer Computations (Plenum Press, New York, 1972), Vol. 43, p. 85.
  2. G. Robins and A. Zelikovsky, Proceedings of the 11th annual ACM-SIAM symposium on Discrete algorithms, 2000 (unpublished), pp. 770–779.
  3. M. Mezard, G. Parisi, and R. Zecchina, Science 297, 812 (2002).
  4. A. Braunstein and R. Zecchina, Phys. Rev. Lett. 96, 030201 (2006).
  5. B. J. Frey and D. Dueck, Science 315, 972 (2007).
  6. A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, and R. Zecchina, Phys. Rev. E 68, 036702 (2003).
  7. A. Braunstein, M. Mezard, and R. Zecchina, Random Struct. Algorithms 27, 201 (2005).
  8. C. Di, A. Montanari, and R. Urbanke, Proceedings of the International Symposium on Information Theory. ISIT 2004, 2004 (unpublished), p. 102.
  9. F. Krzakala, A. Montanari, F. Ricci-Tersenghi, G. Semerjian, and L. Zdeborova, Proc. Natl. Acad. Sci. U.S.A. 104, 10318 (2007).
  10. M. Bayati, C. Borgs, A. Braunstein, J. Chayes, A. Ramezanpour, and R. Zecchina, Phys. Rev. Lett. 101, 037208 (2008).
  11. M. Bayati, C. Borgs, J. Chayes, and R. Zecchina, e-print arXiv:0709.1190;
    12. M. Bayati, C. Borgs, J. Chayes, and R. Zecchina, J. Stat. Mech.: Theory Exp. 2008, L06001.
  12. Y. Weiss, Neural Comput. 12, 1 (2000).
  13. Y. Weiss and W. Freeman, Neural Comput. 13, 2173 (2001).
  14. Y. Weiss and W. Freeman, IEEE Trans. Inf. Theory 47, 736 (2001).
  15. R. Prim, Bell Syst. Tech. J. 36, 1389 (1957).

CITING ARTICLES
For access to citing articles, you need to log in.
For access to citing articles, you need to Log in.


Copyright © American Institute of Physics