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
|
| _version_ | 1797091960221073408 |
|---|---|
| author | Cohen, D Cooper, M Jeavons, P |
| author_facet | Cohen, D Cooper, M Jeavons, P |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | 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 preferences. We focus on valued constraints over Boolean variables, and we establish a dichotomy theorem which characterizes the complexity of any problem involving a fixed set of constraints of this kind. © Springer-Verlag Berlin Heidelberg 2004. |
| first_indexed | 2024-03-07T03:39:48Z |
| format | Journal article |
| id | oxford-uuid:bd81532e-91b0-445d-9d05-e0ba00a90e44 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T03:39:48Z |
| publishDate | 2004 |
| record_format | dspace |
| spelling | oxford-uuid:bd81532e-91b0-445d-9d05-e0ba00a90e442022-03-27T05:32:15ZA complete characterization of complexity for boolean constraint optimization problemsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:bd81532e-91b0-445d-9d05-e0ba00a90e44EnglishSymplectic Elements at Oxford2004Cohen, DCooper, MJeavons, PWe 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 preferences. We focus on valued constraints over Boolean variables, and we establish a dichotomy theorem which characterizes the complexity of any problem involving a fixed set of constraints of this kind. © Springer-Verlag Berlin Heidelberg 2004. |
| spellingShingle | Cohen, D Cooper, M Jeavons, P A complete characterization of complexity for boolean constraint optimization problems |
| title | A complete characterization of complexity for boolean constraint optimization problems |
| title_full | A complete characterization of complexity for boolean constraint optimization problems |
| title_fullStr | A complete characterization of complexity for boolean constraint optimization problems |
| title_full_unstemmed | A complete characterization of complexity for boolean constraint optimization problems |
| title_short | A complete characterization of complexity for boolean constraint optimization problems |
| title_sort | complete characterization of complexity for boolean constraint optimization problems |
| work_keys_str_mv | AT cohend acompletecharacterizationofcomplexityforbooleanconstraintoptimizationproblems AT cooperm acompletecharacterizationofcomplexityforbooleanconstraintoptimizationproblems AT jeavonsp acompletecharacterizationofcomplexityforbooleanconstraintoptimizationproblems AT cohend completecharacterizationofcomplexityforbooleanconstraintoptimizationproblems AT cooperm completecharacterizationofcomplexityforbooleanconstraintoptimizationproblems AT jeavonsp completecharacterizationofcomplexityforbooleanconstraintoptimizationproblems |