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 in...
Expand abstract
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Authors
Funding
Bibliographic Details
- Publisher:
- Schloss Dagstuhl Publisher's website
- Series:
- LIPIcs
- Volume:
- 170
- 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
Item Description
- 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)
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record