Name
Abstract | ||
|---|---|---|
We study hard 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 belief-propagation guided decimation performs poorly. The pair-decimation approach provides a significant improvement. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1088/1742-6596/233/1/012003 | INTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2010 (IW-SMI 2010) |
Keywords | Field | DocType |
satisfiability,constraint satisfaction problem,correlation function | Mathematical optimization,Decimation,Quantum mechanics,Algorithm,Constraint satisfaction problem,Correlation,Mathematics,Hybrid algorithm (constraint satisfaction) | Journal |
Volume | ISSN | Citations |
233 | 1742-6588 | 1 |
PageRank | References | Authors |
0.40 | 5 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Saburo Higuchi | 1 | 1 | 1.07 |
| Marc Mézard | 2 | 590 | 39.09 |