Saburo Higuchi 1, Marc Mézard 2
Journal of statistical mechanics-theory and experiment (2009) P12009
We study hard constraint satisfaction problems with a decimation approach based on message passing algorithms. Decimation induces a renormalization flow in the space of problems, and we exploit the fact that this flow transforms some of the constraints into linear constraints over GF(2). In particular, when the flow hits the subspace of linear problems, one can stop decimation and use Gaussian elimination. We introduce a new decimation algorithm which uses this linear structure and shows a strongly improved performance with respect to the usual decimation methods on some of the hardest locked occupation problems.
- 1. Department of Applied Mathematics and Informatics,
Ryukoku Univsersity - 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
CNRS : UMR8626 – Université Paris XI – Paris Sud