The Power of Sherali--Adams Relaxations for General-Valued CSPs
The Power of Sherali--Adams Relaxations for General-Valued CSPs
We give a precise algebraic characterization of the power of Sherali--Adams relaxations for solvability of valued constraint satisfaction problems (CSPs) to optimality. The condition is that of bounded width, which has already been shown to capture the power of local consistency methods for decision CSPs and the power of semidefinite …