Correlation-based decimation in Constraint Satisfaction Problems
We study bard constraint satisfaction problems using some decimation algorithms based on mean-field approximations. The message-passing approach is used to estimate, beside the usual one-variable marginals, the pair correlation functions. The identification of strongly correlated pairs allows to use a new decimation procedure, where the relative orientation of a pair of variables is fixed. We apply this novel decimation to locked occupation problems, a class of hard constraint satisfaction problems where the usual belicf-propngation guided decimation performs poorly. The pair-decimation approach provides a significant improvement.
Saburo Higuchi Marc Mezard
Laboratoire de Physique Theorique et Modeles Statistiqnes, CNRS and Universite Paris-Sud, Bat 100, 9 Departmcnt of Applied Mathematics and Informatics, Ryukoku University, Otsu, Shiga, 520-2194, Japan
国际会议
International Workshop on Statistical Physics and Computer Sciences(统计物理与计算机科学交叉研究国际研讨会 )
北京
英文
103-115
2010-07-08（万方平台首次上网日期，不代表论文的发表时间）