Abstract:
We study linear programming relaxations of Vertex Cover and Max Cut arising from repeated applications of the ``lift-and-project'' method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that the integrality gap remains at least $2-\epsilon$ after $\Omega_\epsilon(\log n)$ rounds, where $n$ is the number of vertices, and Tourlakis proves that integrality gap remains at least $1.5-\epsilon$ after $\Omega((\log n)^2)$ rounds. Fernandez de la Vega and Kenyon prove that the integrality gap of Max Cut is at most $1/2 + \epsilon$ after any constant number of rounds. (Their result also applies to the more powerful Sherali-Adams method.) We prove that the integrality gap of Vertex Cover remains at least $2-\epsilon$ after $\Omega_\epsilon (n)$ rounds, and that the integrality gap of Max Cut remains at most $1/2 +\epsilon$ after $\Omega_\epsilon(n)$ rounds.

Abstract:
We study linear programming relaxations of Vertex Cover and Max Cut arising from repeated applications of the ``lift-and-project'' method of Lovasz and Schrijver starting from the standard linear programming relaxation. For Vertex Cover, Arora, Bollobas, Lovasz and Tourlakis prove that the integrality gap remains at least $2-\epsilon$ after $\Omega_\epsilon(\log n)$ rounds, where $n$ is the number of vertices, and Tourlakis proves that integrality gap remains at least $1.5-\epsilon$ after $\Omega((\log n)^2)$ rounds. We are not aware of previous work on Lovasz-Schrijver linear programming relaxations for Max Cut. We prove that the integrality gap of Vertex Cover remains at least $2-\epsilon$ after $\Omega_\epsilon (n)$ rounds, and that the integrality gap of Max Cut remains at most $1/2 +\epsilon$ after $\Omega_\epsilon(n)$ rounds. The result for Max Cut shows a gap between the approximation provided by linear versus semidefinite programmming relaxations.