Soft constraints: Complexity and multimorphisms
Over the past few years there has been considerable progress in methods to systematically analyse the complexity of classical (crisp) constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of classical co...
| Հիմնական հեղինակներ: | , , , |
|---|---|
| Ձևաչափ: | Journal article |
| Լեզու: | English |
| Հրապարակվել է: |
2003
|
| _version_ | 1826258411020353536 |
|---|---|
| author | Cohen, D Cooper, M Jeavons, P Krokhin, A |
| author_facet | Cohen, D Cooper, M Jeavons, P Krokhin, A |
| author_sort | Cohen, D |
| collection | OXFORD |
| description | Over the past few years there has been considerable progress in methods to systematically analyse the complexity of classical (crisp) constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of classical constraints to a corresponding set of algebraic operations, known as polymorphisms. In this paper we begin a systematic investigation of the complexity of combinatorial optimisation problems expressed using various forms of soft constraints. We extend the notion of a polymorphism by introducing a more general algebraic operation, which we call a multimorphism. We show that a number of maximal tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms. © Springer-Verlag 2003. |
| first_indexed | 2024-03-06T18:33:34Z |
| format | Journal article |
| id | oxford-uuid:0a79e060-a5a1-4638-9ec0-a28916abddd6 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T18:33:34Z |
| publishDate | 2003 |
| record_format | dspace |
| spelling | oxford-uuid:0a79e060-a5a1-4638-9ec0-a28916abddd62022-03-26T09:24:03ZSoft constraints: Complexity and multimorphismsJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0a79e060-a5a1-4638-9ec0-a28916abddd6EnglishSymplectic Elements at Oxford2003Cohen, DCooper, MJeavons, PKrokhin, AOver the past few years there has been considerable progress in methods to systematically analyse the complexity of classical (crisp) constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of classical constraints to a corresponding set of algebraic operations, known as polymorphisms. In this paper we begin a systematic investigation of the complexity of combinatorial optimisation problems expressed using various forms of soft constraints. We extend the notion of a polymorphism by introducing a more general algebraic operation, which we call a multimorphism. We show that a number of maximal tractable sets of soft constraints, both established and novel, can be characterised by the presence of particular multimorphisms. © Springer-Verlag 2003. |
| spellingShingle | Cohen, D Cooper, M Jeavons, P Krokhin, A Soft constraints: Complexity and multimorphisms |
| title | Soft constraints: Complexity and multimorphisms |
| title_full | Soft constraints: Complexity and multimorphisms |
| title_fullStr | Soft constraints: Complexity and multimorphisms |
| title_full_unstemmed | Soft constraints: Complexity and multimorphisms |
| title_short | Soft constraints: Complexity and multimorphisms |
| title_sort | soft constraints complexity and multimorphisms |
| work_keys_str_mv | AT cohend softconstraintscomplexityandmultimorphisms AT cooperm softconstraintscomplexityandmultimorphisms AT jeavonsp softconstraintscomplexityandmultimorphisms AT krokhina softconstraintscomplexityandmultimorphisms |