The Library
Soft constraints: Complexity and multimorphisms
Tools
Tools
Tools
UNSPECIFIED (2003) Soft constraints: Complexity and multimorphisms. In: 9th International Conference on Principles and Practice of Constraint Programming, KINSALE, IRELAND, SEP 29-OCT 03, 2003. Published in: PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2003, PROCEEDINGS, 2833 pp. 244-258. ISBN 3-540-20202-1. ISSN 0302-9743.
Research output not available from this repository, contact author.Abstract
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.
| Item Type: | Conference Item (UNSPECIFIED) | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
| Series Name: | LECTURE NOTES IN COMPUTER SCIENCE | ||||
| Journal or Publication Title: | PRINCIPLES AND PRACTICE OF CONSTRAINT PROGRAMMING - CP 2003, PROCEEDINGS | ||||
| Publisher: | SPRINGER-VERLAG BERLIN | ||||
| ISBN: | 3-540-20202-1 | ||||
| ISSN: | 0302-9743 | ||||
| Editor: | Rossi, F | ||||
| Official Date: | 2003 | ||||
| Dates: |
|
||||
| Volume: | 2833 | ||||
| Number of Pages: | 15 | ||||
| Page Range: | pp. 244-258 | ||||
| Publication Status: | Published | ||||
| Title of Event: | 9th International Conference on Principles and Practice of Constraint Programming | ||||
| Location of Event: | KINSALE, IRELAND | ||||
| Date(s) of Event: | SEP 29-OCT 03, 2003 |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
