Computer Science – Artificial Intelligence
Scientific paper
2007-09-11
Computer Science
Artificial Intelligence
10 pages, 4 figures, to be presented at Allerton 07, minor revision
Scientific paper
Message passing algorithms have proved surprisingly successful in solving hard constraint satisfaction problems on sparse random graphs. In such applications, variables are fixed sequentially to satisfy the constraints. Message passing is run after each step. Its outcome provides an heuristic to make choices at next step. This approach has been referred to as `decimation,' with reference to analogous procedures in statistical physics. The behavior of decimation procedures is poorly understood. Here we consider a simple randomized decimation algorithm based on belief propagation (BP), and analyze its behavior on random k-satisfiability formulae. In particular, we propose a tree model for its analysis and we conjecture that it provides asymptotically exact predictions in the limit of large instances. This conjecture is confirmed by numerical simulations.
Montanari Andrea
Ricci-Tersenghi Federico
Semerjian Guilhem
No associations
LandOfFree
Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-392855