A complete characterization of complexity for boolean constraint optimization problems
We analyze the complexity of optimization problems expressed using valued constraints. This very general framework includes a number of well-known optimization problems such as MAX-SAT, and WEIGHTED MAX-SAT, as well as properly generalizing the classical CSP framework by allowing the expression of p...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
2004
|