Journal article icon

Journal article

The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains

Abstract:

Convex relaxations have been instrumental in solvability of constraint satisfaction problems (CSPs), as well as in the three different generalisations of CSPs: valued CSPs, infinite-domain CSPs, and most recently promise CSPs. In this work, we extend an existing tractability result to the three generalisations of CSPs combined: We give a sufficient condition for the combined basic linear programming and affine integer programming relaxation for exact solvability of promise valued CSPs over in...

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

Actions


Access Document


Files:
Publisher copy:
10.1145/3458041

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
ORCID:
0000-0002-0263-159X
More from this funder
Name:
Royal Society
Grant:
URF\R\180000
More from this funder
Name:
European Commission
Grant:
714532
Publisher:
Association for Computing Machinery
Journal:
ACM Transactions on Algorithms More from this journal
Volume:
17
Issue:
3
Pages:
1-23
Publication date:
2021-07-12
Acceptance date:
2021-03-20
DOI:
EISSN:
1549-6333
ISSN:
1549-6325
Language:
English
Keywords:
Pubs id:
1168842
Local pid:
pubs:1168842
Deposit date:
2021-03-20

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