论文标题
在无限域上的Promise VCSP的组合基本LP和仿射IP放松
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
论文作者
论文摘要
凸放松在约束满意度问题（CSP）以及CSP的三种不同概括中的可溶性中发挥了作用：有价值的CSP，无限域CSP和最近有望CSP。在这项工作中，我们将现有的障碍结果扩展到了CSP的三个概括：我们为组合的基本线性编程和仿射整数编程放松提供了足够的条件，以确切的有望有价值的CSP在无限域中的确切可溶性。这扩展了Brakensiek和Guruswami [Soda'20]的结果（未价值）CSP（在有限域上）。
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).
