paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The limits of SDP relaxations for general-valued CSPs

一般值 CSP 的 SDP 松弛的极限
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 该论文研究一般值约束满足问题（VCSP）的 SDP/LP 松弛极限与 bounded width 条件，属于理论计算机科学和约束优化的复杂性理论，未涉及静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析，与用户研究方向几乎无交集。引用 6 inbox
Johan Thapper, Stanislav Zivny
逻辑与自动机逻辑与约束编程
crossref: 2026-09-12

AI 速览

一句话：论文研究一般值 CSP 的 SDP 松弛能力极限，并联系 Sherali-Adams LP 层次与 bounded width 条件。

论文关注一般值约束满足问题（VCSP）的 SDP 松弛极限，并将其与 Sherali-Adams LP 层次及 bounded width 条件联系起来。对一般值约束语言 Γ，核心等价刻画为：任意 VCSP(Γ) 实例可用常数层 Sherali-Adams LP 最优求解；当且仅当可用第三层 Sherali-Adams LP 最优求解；当且仅当 Γ 的 support 满足 bounded width 条件，即包含所有元数的 weak near-unanimity 操作。该刻画将 LP 松弛的最优可解性归约为代数不变量，从而为判断 SDP 等更强松弛能否扩大可解范围提供了边界。

问题
研究一般值约束满足问题 VCSP(Γ) 在 SDP/LP 松弛下的可解性边界，特别是哪些约束语言可被常数层松弛最优求解。
方法
通过等价性证明，将 Sherali-Adams LP 层次的可解性与约束语言 support 的 bounded width 代数条件（weak near-unanimity 操作）建立联系。
评估
理论证明与等价刻画：常数层 Sherali-Adams LP、第三层 Sherali-Adams LP 与 bounded width 条件三者等价，并用于限定 SDP 松弛的能力。
原文摘要（Abstract）

It has been shown that for a general-valued constraint language Γ the following statements are equivalent: (1) any instance of VCSP(Γ) can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy; (2) any instance of VCSP(Γ) can be solved to optimality using the third level of the Sherali-Adams LP hierarchy; (3) the support of Γ satisfies the “bounded width condition”, i.e., it contains weak near-unanimity operations of all arities.

链接与引用

DOI 原文 ·

BibTeX 
@inproceedings{paperbot4195,
  title = {The limits of SDP relaxations for general-valued CSPs},
  author = {Johan Thapper and Stanislav Zivny},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005087}
}