Lift & Project Systems Performing on the Partial-Vertex-Cover Polytope

Konstantinos Georgiou, Andy Jiang, Edward Lee +3

We study integrality gap (IG) lower bounds on strong LP and SDP relaxations derived by the Sherali-Adams (SA), Lovasz-Schrijver-SDP (LS+), and Sherali-Adams-SDP (SA+) lift-and-proj…