The approximability of MAX CSP with fixed-value constraints

Vladimir Deineko, Peter Jonsson, Mikael Klasson +1

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to a…