Blog
About

  • 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
      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

      Comments

      Comment on this article