A submodular-based decomposition strategy for valued CSPs
Maher Helaoui, Wady Naanaa · Frontiers in artificial intelligence and applications · 2012
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.