Abstract

H. Xu, C. Cheng, S. Koenig and S. Kumar. Message Passing Algorithms for Semiring-Based and Valued Constraint Satisfaction Problems. In Symposium on Combinatorial Search (SoCS), pages 115-123, 2018.

Abstract: Local consistency algorithms, like arc consistency (AC) algorithms, are polynomial-time algorithms that prune the search space of constraint satisfaction problems (CSPs). In this paper, we present connections between message passing algorithms and AC for semiring-based CSPs (SCSPs) and valued CSPs (VCSPs), two well-established frameworks that generalize CSPs. Message passing algorithms are well known distributed search algorithms for solving many combinatorial problems in artificial intelligence, probabilistic reasoning, and information theory. However, the relationship between message passing algorithms and SCSPs or VCSPs still remains understudied. Towards this end, we propose the best-o message passing (BOMP) algorithm for SCSPs and VCSPs. We prove that, unlike other standard message passing algorithms which are in general not guaranteed to converge, the BOMP algorithm guarantees convergence for SCSPs and specific subclasses of VCSPs. We also theoretically study the relationship between the BOMP algorithm and AC on SCSPs, and empirically study the quality of the solutions produced by the BOMP algorithm for VCSPs.

Download the paper in pdf.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.


This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.