Blog
About

19
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms

      Preprint

      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          We introduce a version of the cavity method for diluted mean-field spin models that allows the computation of thermodynamic quantities similar to the Franz-Parisi quenched potential in sparse random graph models. This method is developed in the particular case of partially decimated random constraint satisfaction problems. This allows to develop a theoretical understanding of a class of algorithms for solving constraint satisfaction problems, in which elementary degrees of freedom are sequentially assigned according to the results of a message passing procedure (belief-propagation). We confront this theoretical analysis to the results of extensive numerical simulations.

          Related collections

          Author and article information

          Journal
          2009-04-22
          10.1088/1742-5468/2009/09/P09001
          0904.3395

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          Custom metadata
          J Stat. Mech. P09001 (2009)
          32 pages, 24 figures
          cond-mat.dis-nn cond-mat.stat-mech cs.DM

          Condensed matter, Discrete mathematics & Graph theory, Theoretical physics

          Comments

          Comment on this article