Supermodular functions and the complexity of MAX CSP
CohenDavid, CooperMartin, JeavonsPeter, KrokhinAndrei · Discrete Applied Mathematics · 2005
In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collectio...