The Library
Hybrid tractability of valued constraint problems
Tools
Cooper, Martin C. and Živný, Stanislav (2011) Hybrid tractability of valued constraint problems. Artificial Intelligence, 175 (9-10). pp. 1555-1569. doi:10.1016/j.artint.2011.02.003 ISSN 0004-3702.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Official URL: http://dx.doi.org/10.1016/j.artint.2011.02.003
Abstract
The constraint satisfaction problem (CSP) is a central generic problem in computer science and artificial intelligence: it provides a common framework for many theoretical problems as well as for many real-life applications. Valued constraint problems are a generalisation of the CSP which allow the user to model optimisation problems. Considerable effort has been made in identifying properties which ensure tractability in such problems. In this work, we initiate the study of hybrid tractability of valued constraint problems; that is, properties which guarantee tractability of the given valued constraint problem, but which do not depend only on the underlying structure of the instance (such as being tree-structured) or only on the types of valued constraints in the instance (such as submodularity). We present several novel hybrid classes of valued constraint problems in which all unary constraints are allowed, which include a machine scheduling problem, constraint problems of arbitrary arities with no overlapping nogoods, and the SoftAllDiff constraint with arbitrary unary valued constraints. An important tool in our investigation will be the notion of forbidden substructures.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Journal or Publication Title: | Artificial Intelligence | ||||
Publisher: | Elsevier BV | ||||
ISSN: | 0004-3702 | ||||
Official Date: | June 2011 | ||||
Dates: |
|
||||
Volume: | 175 | ||||
Number: | 9-10 | ||||
Page Range: | pp. 1555-1569 | ||||
DOI: | 10.1016/j.artint.2011.02.003 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |