Supermodular Functions and the Complexity of MAX CSP
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 collection of constraints which are applied to certain specified subsets of these variables; the goal is to find...
| Main Authors: | , , , |
|---|---|
| Format: | Report |
| Published: |
Oxford University Computing Laboratory
2004
|