Lift & project systems performing on the partial-vertex-cover polytope

摘要

We study integrality gap (IG) lower bounds on strong LP and SDP relaxations derived by the Sherali-Adams (SA), Lovasz-Schrijver-SDP (LS+), Sherali-Adams-SDP (SA(+)), and Lasserre-SDP (La) lift-and-project (L&P) systems for the t-Partial-Vertex-Cover (t-PVC) problem, a variation of the classic Vertex-Cover problem in which only t edges need to be covered. t-PVC admits a 2-approximation using various algorithmic techniques, all relying on a natural LP relaxation. With starting point this LP relaxation, our main results assert that for every epsilon > 0, level-Theta(n) LPs or SDPs derived by all known L&P systems that have been used for positive algorithmic results (but the Lasserre hierarchy) have IGs at least (1 - epsilon)n/t, where n is the number of vertices of the input graph. Our lower bounds are nearly tight, in that level-n relaxations, even of the weakest systems, have integrality gap 1. Additionally, we give a 0 (root n) integrality gap for the Level-1 Lasserre system and a superconstant general integrality gap for all Level-Theta(n) Lasserre derived SDPs.