Search
 
loader loading subjects...
cover
A submodular-based decomposition strategy for valued CSPs
Maher Helaoui, Wady Naanaa
149 - 161
10.3233/978-1-61499-096-3-149
Frontiers in Artificial Intelligence and Applications
Volume 241: STAIRS 2012
Abstract

Valued Constraint Satisfaction Problems (VCSPs) can model many combinatorial problems. VCSPs that involve submodular valuation functions only is a particular class of VCSPs that have the advantage of being tractable. In this paper, we propose a problem decomposition strategy for binary VCSPs which consists in decomposing the problem to be solved into a set of submodular, and then tractable, subproblems. The decomposition strategy combines two problem solving techniques, namely domain partitioning and value permutation.

Download
Creative Commons License