CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation

Part of Advances in Neural Information Processing Systems 20 (NIPS 2007)

Bibtex »Metadata »Paper »


Luis E. Ortiz


<p>This paper proposes constraint propagation relaxation (CPR), a probabilistic approach to classical constraint propagation that provides another view on the whole parametric family of survey propagation algorithms SP(&#961;), ranging from belief propagation (&#961; = 0) to (pure) survey propagation(&#961; = 1). More importantly, the approach elucidates the implicit, but fundamental assumptions underlying SP(&#961;), thus shedding some light on its effectiveness and leading to applications beyond k-SAT.</p>