Journal article icon

Journal article

The complexity of conservative finite-valued CSPs

Abstract:

We study the complexity of valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fixed set of cost functions over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. We consider the case of so-called \emph{conservative} languages; that is, languages containing all unary cost functions, thus allowing arbitrary restrictions on the domains of th...

Expand abstract

Actions


Access Document


Publisher copy:
10.1145/2450142.2450146

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Computer Science
Role:
Author
Journal:
CoRR
Volume:
abs/1008.1555
Issue:
2
Pages:
1-38
Publication date:
2010-08-09
DOI:
EISSN:
1557-735X
ISSN:
0004-5411
URN:
uuid:875df0a6-3da7-4db9-acb3-21900f208869
Source identifiers:
432135
Local pid:
pubs:432135
Language:
English
Keywords:

Terms of use


Metrics


Views and Downloads






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

TO TOP