Susceptibility Propagation for Constraint Satisfaction Problems
arXiv:0903.1621 · doi:10.1088/1742-6596/233/1/012003
Abstract
We study the susceptibility propagation, a message-passing algorithm to compute correlation functions. It is applied to constraint satisfaction problems and its accuracy is examined. As a heuristic method to find a satisfying assignment, we propose susceptibility-guided decimation where correlations among the variables play an important role. We apply this novel decimation to locked occupation problems, a class of hard constraint satisfaction problems exhibited recently. It is shown that the present method performs better than the standard belief-guided decimation.
arXiv comment17 pages, 5 figures
References in corpus (14)
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Phase Transitions in the Coloring of Random Graphs
- Clustering of solutions in the random satisfiability problem
- Coloring random graphs
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Learning by message-passing in networks of discrete synapses
- A variational description of the ground state structure in random satisfiability problems
- Loop Calculus in Statistical Physics and Information Science
- How to Compute Loop Corrections to Bethe Approximation
- On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
- Survey-propagation decimation through distributed local computations
- Locked constraint satisfaction problems
- Constraint satisfaction problems with isolated solutions are hard