Conference item icon

Conference item

The complexity of finite-valued CSPs

Abstract:

Let Γ be a set of rational-valued functions on a fixed finite domain; such a set is called a finite-valued constraint language. The valued constraint satisfaction problem, VCSP(Γ), is the problem of minimising a function given as a sum of functions from Γ. We establish a dichotomy theorem with respect to exact solvability for all finite-valued languages defined on domains of arbitrary finite size.


We show that every core language Γ either admits a binary idempotent and symmetr...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1145/2488608.2488697

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More from this funder
Name:
Seventh Framework Programme
Grant:
257039
Publisher:
Association for Computing Machinery
Host title:
Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC ’13)
Journal:
45th Annual ACM Symposium on Theory of Computing More from this journal
Publication date:
2013-06-01
DOI:
ISSN:
1557-735X and 0004-5411
ISBN:
9781450320290
Keywords:
Pubs id:
pubs:432136
UUID:
uuid:e905dfc2-2e55-45a5-b24f-a5cd98d48743
Local pid:
pubs:432136
Source identifiers:
432136
Deposit date:
2017-03-02

Terms of use


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