Supermodular functions and the complexity of M-AX 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: | , , , |
|---|---|
| פורמט: | Journal article |
| שפה: | English |
| יצא לאור: |
2005
|