Journal article icon

Journal article

The complexity of Boolean surjective general-valued CSPs

Abstract:

Valued constraint satisfaction problems (VCSPs) are discrete optimisation problems with a $\overline{\mathbb{Q}}$-valued objective function given as a sum of fixed-arity functions, where $\overline{\mathbb{Q}}=\mathbb{Q}\cup\{\infty\}$ is the set of extended rationals.

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 ...

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

Actions


Authors


More by this author
Department:
Oxford, Colleges and Halls, Balliol College
More by this author
Department:
Oxford, MPLS, Computer Science
More from this funder
Funding agency for:
Fulla, P
More from this funder
Funding agency for:
Zivny, S
Journal:
arXiv
Publication date:
2017-02-05
Pubs id:
pubs:681714
URN:
uri:b50b5027-2c1f-4aea-999d-a5c23f59129f
UUID:
uuid:b50b5027-2c1f-4aea-999d-a5c23f59129f
Local pid:
pubs:681714
Keywords:

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