Linear and semidefinite programming are highly successful approaches for obtaining good approximations for NP-hard optimization problems. For example, breakthrough approximation algorithms for MAX CUT and SPARSEST CUT use semidefinite programming.

Perhaps the most prominent NP-hard problem whose exact approximation factor is still unresolved is VERTEX COVER. PCP-based techniques of Dinur and Safra [7] show that it is not possible to achieve a factor better than 1.36; on the other hand no known algorithm does better than the factor of 2 achieved by the simple greedy algorithm. Furthermore, there is a widespread belief that SDP techniques are the most promising methods available for improving upon this factor of 2.

Following a line of study initiated by Arora et al. [3], our aim is to show that a large family of LP and SDP based algorithms fail to produce an approximation for VERTEX COVER better than 2. Lovész and Schrijver [21] introduced the systems LS and LS_ + for systematically tightening LP and SDP relaxations, respectively, over many rounds. These systems naturally capture large classes of LP and SDP relaxations; indeed, LS_ + captures the celebrated SDP-based algorithms for MAX CUT and SPARSEST CUT mentioned above.

We rule out polynomial-time 2 - \Omega (1) approximations for VERTEX COVER using LS_ +. In particular, we prove an integrality gap of 2-o(1) for VERTEX COVER SDPs obtained by tightening the standard LP relaxation with \Omega (\sqrt {\log n/\log \log n} ) rounds of LS_ +. While tight integrality gaps were known for VERTEX COVER in the weaker LS system [23], previous results did not rule out a 2 - \Omega (1) approximation after even two rounds of LS_ +.