Journal article icon

Journal article

The complexity of soft constraint satisfaction

Abstract:

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the complexity of a set of constraints to a corresponding set of algebraic operations, known as polymorphisms. In this paper we extend the analysis of complexity to the more general framework of combinatorial optimisation problems expressed using various...

Expand abstract
Publication status:
Published

Actions


Access Document


Files:
Publisher copy:
10.1016/j.artint.2006.04.002

Authors


Cooper, MC More by this author
More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Krokhin, AA More by this author
Journal:
ARTIFICIAL INTELLIGENCE
Volume:
170
Issue:
11
Pages:
983-1016
Publication date:
2006-08-05
DOI:
ISSN:
0004-3702
URN:
uuid:39b3409a-2b16-45b6-a32f-756289499e51
Source identifiers:
284843
Local pid:
pubs:284843

Terms of use


Metrics



If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP