A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
复制标题
顶点覆盖Lovasz-Schrijver SDP松弛的线性圆下界
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Madhur Tulsiani
中科院分区：
文献类型：
--
作者：
Grant Schoenebeck;Luca Trevisan;Madhur Tulsiani
从标准的线性规划松弛出发，研究了重复应用Lovasz和Schrijver的LS+“Lift-and-Project”方法所产生的顶点覆盖的半定规划松弛。Goemans和Kleinberg证明了在一轮LS+之后，积分间隙保持任意接近于2。Charikar证明了积分间隙为2，后来被Hatami，Magen和Markakis加强，以获得更强的松弛，然而，这是两轮LS+所无法比拟的。Georgiou，Magen，Pitassi和Tourlakis的后续工作表明，在Omega(根对数n-log n)轮之后，完整性缺口仍然是2-epsiv[？]。我们证明了在倒数n轮之后，整性间隙至少保持7/6-epsiv，其中n是顶点数，而cepsiv>；0是一个只依赖于epsiv的常数。
We study semidefinite programming relaxations of Vertex Cover arising from repeated applications of the LS+ "lift-and-project" method of Lovasz and Schrijver starting from the standard linear programming relaxation. Goemans and Kleinberg prove that after one round of LS+ the integrality gap remains arbitrarily close to 2. Charikar proves an integrality gap of 2, later strengthened by Hatami, Magen, and Markakis, for stronger relaxations that are, however, incomparable with two rounds of LS+. Subsequent work by Georgiou, Magen, Pitassi, and Tourlakis shows that the integrality gap remains 2 -epsiv after Omega (radiclog n-log log n ) rounds [?]. We prove that the integrality gap remains at least 7/6 - epsiv after cepsivn rounds, where n is the number of vertices and cepsiv > 0 is a constant that depends only on epsiv.