From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
From Weak to Strong Linear Programming Gaps for All Constraint Satisfaction Problems
复制标题
所有约束满足问题的从弱到强的线性规划差距
DOI：
10.4086/toc.2018.v014a010
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
Mrinalkanti Ghosh;Madhur Tulsiani
研究了约束满足问题（CSP）的线性规划（LP）松弛逼近问题。我们表明，对于每个CSP，通过基本LP松弛获得的近似至少与使用Sherali-Adams层次的c · logn/ log logn水平（对于某些常数c > 0）在大小为n的实例上给出的松弛获得的近似一样强。Chan等人[FOCS 2013]（最近由Kothari等人[STOC 2017]加强）证明，对于CSP，任何多项式大小的LP扩展公式最多与由Sherali-Adams层次的常数数量的水平获得的松弛一样强（其中水平的数量取决于大小界限中多项式的指数）。将此与我们的结果结合还意味着任何多项式大小的LP扩展公式最多与基本LP一样强，这可以被认为是第32届计算复杂性会议（CCC'17）论文集中出现的本文的会议版本的基础水平[14]。* NSF奖号CCF-1254044。†NSF奖项编号CCF-1254044。ACM分类：F.2.2、G.1.6 AMS分类：68 Q17、90 C 05
We study the approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations. We show that for every CSP, the approximation obtained by a basic LP relaxation is at least as strong as the approximation obtained using relaxations given by c · logn/ log logn levels of the Sherali–Adams hierarchy (for some constant c > 0) on instances of size n. It was proved by Chan et al. [FOCS 2013] (and recently strengthened by Kothari et al. [STOC 2017]) that for CSPs, any polynomial-size LP extended formulation is at most as strong as the relaxation obtained by a constant number of levels of the Sherali–Adams hierarchy (where the number of levels depend on the exponent of the polynomial in the size bound). Combining this with our result also implies that any polynomial-size LP extended formulation is at most as strong as the basic LP, which can be thought of as the base level of A conference version of this paper appeared in the Proceedings of the 32nd Computational Complexity Conference (CCC’17) [14]. ∗NSF award number CCF-1254044. †NSF award number CCF-1254044. ACM Classification: F.2.2, G.1.6 AMS Classification: 68Q17, 90C05