Node and Arc Consistency in Weighted CSP

Javier Larrosa, Universitat Politecnica de Catalunya

Recently, a general definition of arc consistency (AC) for soft constraints has been proposed. In this paper we specialize this definition to weighted CSP and introduce a O(ed3) algorithm. Then, we refine the definition and introduce a stronger form of arc consistency (AC*) along with a O(n2 d3) algorithm. We empirically demonstrate that AC* is likely to be much better than AC in terms of pruned values.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.