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 infinite-domains. This extends a result of Brakensiek and Guruswami [SODA’20] for promise (non-valued) CSPs (on finite domains).
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, 467.9KB, Terms of use)
-
- Publisher copy:
- 10.1145/3458041
Authors
- 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
- Copyright holder:
- Association for Computing Machinery
- Copyright date:
- 2021
- Rights statement:
- © 2021 Association for Computing Machinery
- Notes:
- This is the accepted manuscript version of the article. The final version is available from the Association for Computer Machinery at: https://doi.org/10.1145/3458041
If you are the owner of this record, you can report an update to it here: Report update to this record