Copyright © 2008 The Institute of Electronics, Information and Communication Engineers
Special Section on Foundations of Computer Science -- Letters -- Algorithm Theory |
Survey Propagation as "Probabilistic Token Passing"
1 The authors are with the School of Information Technology and Engineering, University of Ottawa, 800 King Edward Ave., Ottawa, Ontario, Canada K1N 6N5. E-mail: rtu{at}site.uottawa.ca; yymao{at}site.uottawa.ca; jyzhao{at}site.uottawa.ca
In this paper, we present a clean and simple formulation of survey propagation (SP) for constraint-satisfaction problems as "probabilistic token passing". The result shows the importance of extending variable alphabets to their power sets in designing SP algorithms.
Key Words: constraint-satisfaction problem, survey propagation, graph coloring, message-passing
Manuscript received March 6, 2007.
Reference
[1] M. Mézard, G. Parisi, and R. Zecchina, "Analytic and algorithmic solution of random satisfiability problems," Science, no.297, pp.812–815, 2002. [2] A. Braunstein, R. Mulet, A. Pagnani, M. Weigt, and R. Zecchina, "Polynomial iterative algorithms for coloring and analyzing random graphs," Phys. Rev. E, vol.68, no.3, 036702, 2003. [3] M.J. Wainwright and E. Maneva,"Lossy source encoding via message-passing and decimation over generalized codewords of LDGM codes," Proc. IEEE Int. Symp. Inform. Theory, pp.1493–1497, Adelaide, Australia, 2005. [4] W. Yu and M. Aleksic, "Coding for the blackwell channel: A survey propagation approach," Proc. IEEE Int. Symp. Inform. Theory, pp.1583–1587, Adelaide, Australia, 2005. [5] A. Brauntein, M. Mézard, M. Weight, and R. Zecchina, "Constraint satisfaction by survey propagation," in Computational Complexity and Statistical Physics, ed. A. Percus, G. Istrate, and C. Moore, pp.107–124, Oxford University Press, 2003. [6] A. Braunstein and R. Zeccchina, "Survey propagation as local equilibrium equations," J. Stat. Mech., issue 06, p.06007, June 2004. [7] E. Maneva, E. Mossel, and M.J. Wainwright, "A new look at survey propagation and its generalizations," SODA, pp.1089–1098, 2005. [8] R. Tu, Y. Mao, and J. Zhao, "On generalized survey propagation: Normal realization and sum-product interpretation," Proc. IEEE Int. Symp. Inform. Theory, pp.2042–2046, 2006. [9] F.R. Kschischang, B.J. Frey, and H.-A. Loeliger, "Factor graphs and the sum-product algorithm," IEEE Trans. Inf. Theory, vol.47, no.2, pp.498–519, 2001.
CiteULike 
Connotea 
Del.icio.us What's this?
This Article 
Abstract
Full Text (PDF)
Alert me when this article is cited
Alert me if a correction is posted
Services
Email this article to a friend
Similar articles in this journal
Alert me to new issues of the journal
Add to My Personal Archive
Download to citation manager
Request Permissions
Google Scholar
Articles by TU, R.
Articles by ZHAO, J.
Search for Related Content
Social Bookmarking
What's this?