CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation
Abstract
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(ρ), ranging from belief propagation (ρ = 0) to (pure) survey propagation(ρ = 1). More importantly, the approach elucidates the implicit, but fundamental assumptions underlying SP(ρ), thus shedding some light on its effectiveness and leading to applications beyond k-SAT.
Cite
Text
Ortiz. "CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation." Neural Information Processing Systems, 2007.Markdown
[Ortiz. "CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation." Neural Information Processing Systems, 2007.](https://mlanthology.org/neurips/2007/ortiz2007neurips-cpr/)BibTeX
@inproceedings{ortiz2007neurips-cpr,
title = {{CPR for CSPs: A Probabilistic Relaxation of Constraint Propagation}},
author = {Ortiz, Luis E.},
booktitle = {Neural Information Processing Systems},
year = {2007},
pages = {1113-1120},
url = {https://mlanthology.org/neurips/2007/ortiz2007neurips-cpr/}
}