Conference item icon

Conference item

The complexity of Boolean surjective general-valued CSPs

Abstract:

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with the objective function given as a sum of fixed-arity functions; the values are rational numbers or infinity. In Boolean surjective VCSPs variables take on labels from D={0,1} and an optimal assignment is required to use both labels from D. A classic example is the global min-cut problem in graphs. Building on the work of Uppman, we establish a dichotomy theorem and thus give a complete complexity classific...

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

Actions


Access Document


Files:
Publisher copy:
10.4230/LIPIcs.MFCS.2017.4

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Computer Science
Role:
Author
Royal Society More from this funder
Publisher:
Schloss Dagstuhl Publisher's website
Journal:
International Symposium on Mathematical Foundations of Computer Science Journal website
Volume:
83
Pages:
4:1--4:14
Series:
Leibniz International Proceedings in Informatics
Host title:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Publication date:
2017-11-22
Acceptance date:
2017-06-12
DOI:
ISSN:
1868-8969
Source identifiers:
702642
ISBN:
9783959770460
Keywords:
Pubs id:
pubs:702642
UUID:
uuid:50791649-f98b-48e2-9cf5-b89754833ef7
Local pid:
pubs:702642
Deposit date:
2017-07-01

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