Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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.

Full text not available from this repository, contact author.

Request Changes to record.

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:
DateEvent
2003UNSPECIFIED
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 View Item
twitter

Email us: publications@live.warwick.ac.uk
Contact Details
About Us