Survey propagation as local equilibrium equations Export

@article{citeulike:1436867, abstract = {It has been shown experimentally that a decimation algorithm based on survey propagation\~{}(SP) equations allows one to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum\–product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value\—*\—when they are not forced by the combinatorial constraints. An appropriate \‘local equilibrium condition\’ cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for random K -SAT or random graph colouring (where it is conjectured to be exact) and help to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact.}, author = {Braunstein, Alfredo and Zecchina, Riccardo}, citeulike-article-id = {1436867}, citeulike-linkout-0 = {http://dx.doi.org/10.1088/1742-5468/2004/06/P06007}, citeulike-linkout-1 = {http://stacks.iop.org/1742-5468/2004/i=6/a=P06007}, doi = {10.1088/1742-5468/2004/06/P06007}, journal = {Journal of Statistical Mechanics: Theory and Experiment}, keywords = {cavity-method, constraints, inference, optimization, propagation}, number = {06}, posted-at = {2007-07-24 11:01:21}, priority = {2}, title = {Survey propagation as local equilibrium equations}, url = {http://dx.doi.org/10.1088/1742-5468/2004/06/P06007}, volume = {2004}, year = {2004} }

TY - JOUR ID - citeulike:1436867 L3 - citeulike-article-id:1436867 N2 - It has been shown experimentally that a decimation algorithm based on survey propagation~(SP) equations allows one to solve efficiently some combinatorial problems over random graphs. We show that these equations can be derived as sum\–product equations for the computation of marginals in an extended space where the variables are allowed to take an additional value\—*\—when they are not forced by the combinatorial constraints. An appropriate \‘local equilibrium condition\’ cost/energy function is introduced and its entropy is shown to coincide with the expected logarithm of the number of clusters of solutions as computed by SP. These results may help to clarify the geometrical notion of clusters assumed by SP for random K -SAT or random graph colouring (where it is conjectured to be exact) and help to explain which kind of clustering operation or approximation is enforced in general/small sized models in which it is known to be inexact. IS - 06 JF - Journal of Statistical Mechanics: Theory and Experiment TI - Survey propagation as local equilibrium equations VL - 2004 KW - cavity-method KW - constraints KW - inference KW - optimization KW - propagation AU - Braunstein, Alfredo AU - Zecchina, Riccardo PY - 2004/// UR - http://dx.doi.org/10.1088/1742-5468/2004/06/P06007 ER -