Conference item
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, Version of record, 513.2KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.MFCS.2020.85
Authors
- Publisher:
- Schloss Dagstuhl
- Volume:
- 170
- Series:
- LIPIcs
- Publication date:
- 2020-08-18
- Acceptance date:
- 2020-06-29
- Event title:
- 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
- Event website:
- http://mfcs.mff.cuni.cz/2020/
- Event start date:
- 2020-08-24
- Event end date:
- 2020-08-28
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959771597
- Language:
-
English
- Keywords:
- Pubs id:
-
1115231
- Local pid:
-
pubs:1115231
- Deposit date:
-
2020-06-30
Terms of use
- Copyright holder:
- Viola and Živný
- Copyright date:
- 2020
- Rights statement:
- © Caterina Viola and Stanislav Živný; licensed under Creative Commons License CC-BY.
- Notes:
- This paper was presented at the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), August 2020.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record